- Path Sum IIGiven a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.Recursive Solutionclass Solution { public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> list = new LinkedList<>(); List<Integer> path = new LinkedList<>(); pathSumHelper(list, path, root, sum); return list; } public void pathSumHelper(List<List<Integer>> list, List<Integer> path, TreeNode root, int sum) { if (root == null) return; path.add(root.val); if (root.left == null && root.right == null) { if (root.val == sum) list.add(new LinkedList(path)); path.remove(path.size()-1); return; } pathSumHelper(list, path, root.left, sum-root.val); pathSumHelper(list, path, root.right, sum-root.val); path.remove(path.size()-1); }}DFS Solutionclass Solution { public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> list = new LinkedList<>(); if (root == null) return list; List<Integer> path = new LinkedList<>(); Stack<TreeNode> stack = new Stack<>(); int sumP = 0; TreeNode curNode = root; TreeNode visitedNode = null; while(curNode != null || !stack.isEmpty()) { while (curNode != null) { stack.push(curNode); sumP += curNode.val; path.add(curNode.val); curNode = curNode.left; } curNode = stack.peek(); if (curNode.right == null || curNode.right == visitedNode) { if (curNode.left == null && curNode.right == null && sumP == sum) list.add(new LinkedList(path)); stack.pop(); visitedNode = curNode; sumP -= curNode.val; path.remove(path.size()-1); curNode = null; } else curNode = curNode.right; } return list; }}235. Lowest Common Ancestor of a Binary Search TreeGiven a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”Recursive Solutionclass Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if ((root.val-p.val)*(root.val-q.val) <= 0) return root; if (root.val > p.val) return lowestCommonAncestor(root.left, p, q); return lowestCommonAncestor(root.right, p, q); }}DFS Solutionclass Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { while((root.val-p.val) * (root.val-q.val) > 0) { if (root.val > p.val) root = root.left; else root = root.right; } return root; }}404. Sum of Left LeavesFind the sum of all left leaves in a given binary tree.BFS Solutionclass Solution { public int sumOfLeftLeaves(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); int sum = 0; if (root == null || root.left == null && root.right == null) return sum; queue.offer(root); while(!queue.isEmpty()) { TreeNode node = queue.poll(); TreeNode left = node.left; if (left != null) { if (left.left == null && left.right == null) // no need to enqueue the node sum += left.val; else queue.offer(node.left); } if (node.right != null) queue.offer(node.right); } return sum; }}Recursive Solutionclass Solution { public int sumOfLeftLeaves(TreeNode root) { if (root == null || root.left == null && root.right == null) return 0; if (root.left != null && root.left.left == null && root.left.right == null) return root.left.val + sumOfLeftLeaves(root.right); return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right); }}108. Convert Sorted Array to Binary Search TreeGiven an array where elements are sorted in ascending order, convert it to a height balanced BST.For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.Recursive Solutionclass Solution { public TreeNode sortedArrayToBST(int[] nums) { if(nums == null || nums.length == 0) return null; return getRootHelper(nums, 0, nums.length - 1); } private TreeNode getRootHelper(int[] nums, int low, int high) { if (low > high) return null; int mid = (high-low)/2 + low; TreeNode root = new TreeNode(nums[mid]); root.left = getRootHelper(nums, low, mid-1); root.right = getRootHelper(nums, mid+1, high); return root; }}Iterative: using stackclass Solution { private class Node { TreeNode node; int left, right; public Node(TreeNode node, int left, int right) { this.node = node; this.left = left; this.right = right; } } public TreeNode sortedArrayToBST(int[] nums) { if (nums == null || nums.length == 0) return null; Stack<Node> stack = new Stack<>(); TreeNode root = new TreeNode(0); Node node = new Node(root, 0, nums.length - 1); stack.push(node); while (!stack.isEmpty()) { Node cur = stack.pop(); int mid = (cur.right - cur.left) / 2 + cur.left; cur.node.val = nums[mid]; if (mid > cur.left) { cur.node.left = new TreeNode(0); Node lNode = new Node(cur.node.left, cur.left, mid - 1); stack.push(lNode); } if (mid < cur.right) { cur.node.right = new TreeNode(0); Node rNode = new Node(cur.node.right, mid + 1, cur.right); stack.push(rNode); } } return root; }}