113. Path Sum II
Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.
Recursive Solution
class 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 Solution
class 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 Tree
Given 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 Solution
class 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 Solution
class 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 Leaves
Find the sum of all left leaves in a given binary tree.
BFS Solution
class 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 Solution
class 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 Tree
Given 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 Solution
class 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 stack
class 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;
}
}