[廣告]分治/遞歸 思想總結(jié)：http://www.reibang.com/p/6c1de969830c
- Symmetric Tree
[post-order]Recursive check
class Solution1 {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return isSymmHelper(root.left, root.right);
}
private boolean isSymmHelper(TreeNode left, TreeNode right) {
if(left == null || right == null) return left == right;
if(left.val != right.val) return false;
return isSymmHelper(left.left, right.right) &&isSymmHelper(left.right, right.left);
}
}
- Maximum Depth of Binary Tree
Recursive[遞歸post-order 分治Divide&Conquer dfs來(lái)upwards累積]
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
}
- Balanced Binary Tree
Recusive[遞歸post-order dfs 分治Divide&Conquer 來(lái)upwards累積height]
class Solution {
public boolean isBalanced(TreeNode root) {
return dfsHeight(root) != -1;
}
private int dfsHeight(TreeNode root) {
// post-order dfsly check from left-bottom and accumulate max_height upwards
// meanwhile, check if |left_height - right_height)| > 1 for early stop
if(root == null) return 0;
int left_height = dfsHeight(root.left);
if(left_height == -1) return -1;
int right_height = dfsHeight(root.right);
if(right_height == -1) return -1;
if(Math.abs(left_height - right_height) > 1) return -1;
return Math.max(left_height, right_height) + 1;
}
}
- Minimum Depth of Binary Tree
遞歸post-order 分治Divide&Conquer dfs來(lái)upwards累積
class Solution {
public int minDepth(TreeNode root) {
if(root == null) return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
return (left == 0 || right == 0) ? left + right + 1: Math.min(left,right) + 1;
}
}
- Binary Tree Postorder Traversal
Recursive
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new LinkedList<Integer>();
postHelper(root, list);
return list;
}
public void postHelper(TreeNode root, List<Integer> list) {
if(root == null) return;
postHelper(root.left, list);
postHelper(root.right, list);
list.add(root.val);
}
}
- Count Univalue Subtrees [good example]
遞歸 post-order 分治Divide&Conquer upwards上傳
public class Solution {
public int countUnivalSubtrees(TreeNode root) {
int[] count = new int[1];
helper(root, count);
return count[0];
}
private boolean helper(TreeNode node, int[] count) {
if (node == null) return true;
// divide
boolean left = helper(node.left, count);
boolean right = helper(node.right, count);
// conquer (ifSame(boolean left, boolean right), int count),
// and uploads ifSame & count
if (left && right) {
if (node.left != null && node.val != node.left.val) {
return false;
}
if (node.right != null && node.val != node.right.val) {
return false;
}
count[0]++;
return true;
}
return false;
}
}
- Closest Binary Search Tree Value
Recursive[遞歸(類似post-order) dfs來(lái)upwards累積]
class Solution {
public int closestValue(TreeNode root, double target) {
TreeNode next = target < root.val ? root.left : root.right;
if(next == null) return root.val;
int val_found = closestValue(next, target);
return Math.abs(val_found - target) < Math.abs(root.val - target) ? val_found : root.val;
}
}
- Largest BST Subtree
遞歸 Post-order 分治 Bottom-up向上傳遞
pack傳遞可以通過(guò)返回值 寫(xiě)法1_a，也可以通過(guò)參數(shù) 寫(xiě)法1_b，都可以的
class Solution1_a {
class Pack {
int lower;
int upper;
int count;
Pack(int lower, int upper, int count) {
this.lower = lower;
this.upper = upper;
this.count = count;
}
}
private int result;
public int largestBSTSubtree(TreeNode root) {
result = 0;
helper(root);
return result;
}
private Pack helper(TreeNode root) {
if(root == null) return new Pack(Integer.MAX_VALUE, Integer.MIN_VALUE, 0);
// divide
// [min, max, count]
Pack left = helper(root.left);
Pack right = helper(root.right);
// conquer
Pack pack = new Pack(Integer.MAX_VALUE, Integer.MIN_VALUE, 1);
if(left.count != -1 && right.count != -1 && root.val > left.upper && root.val < right.lower) {
pack.count += (left.count + right.count);
if(pack.count > result) result = pack.count;
}
else {
//locked
return new Pack(0, 0, -1);
}
pack.lower = Math.min(left.lower, root.val);
pack.upper = Math.max(right.upper, root.val);
return pack;
}
}
class Solution1_b {
class Pack {
int lower;
int upper;
int count;
Pack(int lower, int upper, int count) {
this.lower = lower;
this.upper = upper;
this.count = count;
}
}
private int result;
public int largestBSTSubtree(TreeNode root) {
result = 0;
helper(root, new Pack(Integer.MAX_VALUE, Integer.MIN_VALUE, 0));
return result;
}
private void helper(TreeNode root, Pack pack) {
if(root == null) return;
// divide
// [min, max, count]
Pack left = new Pack(Integer.MAX_VALUE, Integer.MIN_VALUE, 0);
Pack right = new Pack(Integer.MAX_VALUE, Integer.MIN_VALUE, 0);
helper(root.left, left);
helper(root.right, right);
pack.count = 1;
if(left.count != -1 && right.count != -1 && root.val > left.upper && root.val < right.lower) {
pack.count += (left.count + right.count);
if(pack.count > result) result = pack.count;
}
else {
//locked
pack.lower = 0;
pack.upper = 0;
pack.count = -1;
}
pack.lower = Math.min(left.lower, root.val);
pack.upper = Math.max(right.upper, root.val);
}
}
- House Robber III
[DP思想] 遞歸 Post-order 分治 Bottom-up向上傳遞
class Solution {
class Result {
int cur_max;
int prev_max;
Result(int cur_max, int prev_max) {
this.cur_max = cur_max;
this.prev_max = prev_max;
}
}
public int rob(TreeNode root) {
Result result = dfsHelper(root);
return Math.max(result.cur_max, result.prev_max);
}
private Result dfsHelper(TreeNode node) {
if(node == null) return new Result(0, 0);
Result left = dfsHelper(node.left);
Result right = dfsHelper(node.right);
// consider this one
int cur_max = left.prev_max + right.prev_max + node.val;
// if including negative case
// int cur_max = Math.max(left.prev_max + right.prev_max, Math.max(left.prev_max, right.prev_max)) + node.val;
// don't consider this one
int prev_max = Math.max(left.cur_max, left.prev_max) + Math.max(right.cur_max, right.prev_max);
Result result = new Result(cur_max, prev_max);
return result;
}
}
- Find Leaves of Binary Tree
遞歸 Post-order 分治 Bottom-up向上傳遞
class Solution {
public List<List<Integer>> findLeaves(TreeNode root) {
// build result list
List<List<Integer>> result = new ArrayList<List<Integer>>();
// bottom-up dfs
dfsHelper(result, root);
return result;
}
private int dfsHelper(List<List<Integer>> result, TreeNode node) {
if(node == null) return -1;
int max_dist = 1 + Math.max(dfsHelper(result, node.left), dfsHelper(result, node.right));
if(max_dist > result.size() - 1) result.add(new ArrayList<Integer>());
result.get(max_dist).add(node.val);
return max_dist;
}
}
- Most Frequent Subtree Sum
Recursive
private int postOrder(TreeNode root) {
if (root == null) return 0;
int left = postOrder(root.left);
int right = postOrder(root.right);
int sum = left + right + root.val;
int count = sumToCount.getOrDefault(sum, 0) + 1;
sumToCount.put(sum, count);
maxCount = Math.max(maxCount, count);
return sum;
}
