- 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;
}
}- 543. Diameter of Binary Tree
Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
分析：一棵树中最长的路径有且仅有两种情况：经过根节点和不经过根节点。
而经过任意一个节点的最长路径一定等于左右子树的最大深度之和。
up to bottom
class Solution {
public int diameterOfBinaryTree(TreeNode root) {
if (root == null) return 0;
int pathRoot = maxDepth(root.left) + maxDepth(root.right);
int tmp = Math.max(diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right));
return Math.max(tmp, pathRoot);
}
private int maxDepth(TreeNode root) {
if (root == null) return 0;
int ldepth = maxDepth(root.left);
int rdepth = maxDepth(root.right);
return Math.max(ldepth, rdepth) + 1;
}
}但是这种解法中，每call一次都会把当前节点的所有子节点遍历一遍，有大量重复的计算，时间复杂度为O(NN)~O(NlgN)（取决于树的高度）
bottom to up
class Solution {
private int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxDepth(root);
return max;
}
private int maxDepth(TreeNode root) {
if (root == null) return 0;
int ldepth = maxDepth(root.left);
int rdepth = maxDepth(root.right);
max = Math.max(max, ldepth + rdepth);
return Math.max(ldepth, rdepth) + 1;
}
}这个解法的核心就在于：max = Math.max(max, ldepth + rdepth)这一句，括号中max记录的是该节点左右两节点中最大路径的值，取它和经过该节点的最大路径中的最大值记录到max中，所以我们在调用函数时就不需要再把子节点再遍历一遍求深度，因为已经记录在max中了。该算法的时间复杂度为O(N)。
