Top-Down(Divde and Conquer)

这里列举更多的是用分治算法来搜索需要的结果，同样的思维运用在Tree transfer中也有体现

算法思维：派小兵帮忙去搜索，一遇到分叉就影分身，走到底之后开始返回，逐层向上汇报结果，直到最顶。

这里的分治做法基本能解决所有的Tree 的性质的问题

很重要： 碰到二叉树的问题，就想想整棵树在该问题上的结果 和左右儿子在该问题上的结果 之间的联系是什么

Maximum VS Minimum Depth of Binary Tree

1. 这里就是分开左右子树去找。典型的分治做法
2. 左右儿子的结果 和 Root 上的关系是：左右子树中的最大值 + 1 = 当前节点的最大深度

public int maxDepth(TreeNode root) {
     if (root == null) return 0;
     return Math.max(maxDepth(root.right), maxDepth(root.left)) + 1;
 }
public int minDepth(TreeNode root) {
     if (root == null)     return 0;
     if (root.left == null)    return minDepth(root.right) + 1;
     if (root.right == null)     return minDepth(root.left) + 1;
     return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
 }

Sum of Left Leaves

public int sumOfLeftLeaves(TreeNode root) {
     int sum = 0;
     if (root == null) return 0;
     if (root.left != null)
         if (root.left.left == null && root.left.right == null)
             sum += root.left.val;
         else
             sum += sumOfLeftLeaves(root.left);
     if (root.right != null)
         sum += sumOfLeftLeaves(root.right);
     return sum;
 }

Same Tree VS Symmetric Tree

public boolean isSymmetric(TreeNode root) {
     if (root == null) return true;
     return helper(root.left, root.right);
}
private boolean helper(TreeNode left, TreeNode right) {
     if (left == null && right == null) return true;
     if (left == null || right == null) return false;
     if (left.val != right.val) return false;
     return helper(left.right, right.left) && helper(left.left, right.right);
}

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null) return false;
    return q.val == p.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

Lowest Common Ancestor of a Binary Tree

• Send information to upper level: current node is p or q's LCA, or neither p nor q.
• If Tree is BST, p and q's LCA must satisfy p < root < q
  • q < root && p < root go left
  • q > root && p > root go right
• other mean: Find distance between two given keys of a Binary Tree

  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
     if (root == null || root == p || root == q) {
         return root;
     }
     TreeNode left = lowestCommonAncestor(root.left, p, q);
     TreeNode right = lowestCommonAncestor(root.right, p, q);

     return left == null ? right : right == null ? left : root;
  }

Balanced Binary Tree

1. 这道题是很典型的两种遍历方式不同会造成不同的复杂度
2. 简单调用depth这样会让复杂度很高，需要在遍历的时候保存当前的节点的信息（是否平衡，当前的节点的深度）

class ResultType { 
    public boolean isBalanced; 
    public int maxDepth; 
    public ResultType(boolean isBalanced, int maxDepth) { 
        this.isBalanced = isBalanced; 
        this.maxDepth = maxDepth; 
    } 
} 
public boolean isBalanced(TreeNode root) { 
    return helper(root).isBalanced; 
} 
private ResultType helper(TreeNode root) { 
    if (root == null) return new ResultType(true, 0); 
    ResultType left = helper(root.left); 
    ResultType right = helper(root.right);             // subtree not balance 
    if (!left.isBalanced || !right.isBalanced) {       // root not balance 
        return new ResultType(false, -1); 
    } 
    if (Math.abs(left.maxDepth - right.maxDepth) > 1) { 
        return new ResultType(false, -1); 
    } 
    return new ResultType(true, Math.max(left.maxDepth, right.maxDepth) + 1); 
}

Count Complete Tree Nodes

• 这里为什么数左右子树都是可以用getHeight来实现？
• 复杂度为多少？

public int countNodes(TreeNode root) {
    if (root == null) return 0;
    int hleft = getHeight(root.left);
    int hright = getHeight(root.right);

    if (hleft == hright) {
        return (1 << hleft) + countNodes(root.right);
    } else {
        return (1 << hright) + countNodes(root.left);
    }
}
private int getHeight(TreeNode root) {
    if (root == null) return 0;
    return getHeight(root.left) + 1;
}

Count Univalue Subtrees

• 向upper level 传递信息：
  • subTree 是否也是univalue(boolean)
  • 当前所有univalue SubTree 个数(int res)
  • 不需要传递当前SubTree的Univalue具体是什么(int value)
• 处理当前level：
  • LeftSubTree 或者 RightSubTree 只要其中之一不是Univalue 即返回False
  • Value of left or Value of right != Value of root return False
  • Rest of conditions will be True, and plus one in res

public int countUnivalSubtrees(TreeNode root) {
    int[] res = new int[1];
    helper(root, res);
    return res[0];
}
private boolean helper(TreeNode root, int[] res) {
    if (root == null) return true;
    boolean left = helper(root.left, res);
    boolean right = helper(root.right, res);

    if (left & right) {                 // think about all sitations!!!
        if (root.left != null && root.val != root.left.val) return false;
        if (root.right != null && root.val != root.right.val) return false;
        res[0]++;
        return true;
    }
    return false;
}

Most Frequent Subtree Sum

Information needed in upper level:

• Sum of Subtree = Sum of leftSubTree + Sum of right SubTree
• Do not need to send LeftSum and RightSum, cuz lower level already did it
• Record Frequency information in Map

Tips:

• TreeMap's Natural Order will help us to sort the Frequency First one is least one
• Initialize TreeMapTreeMap<Integer, List<Integer>> freqMap = new TreeMap<>();
  • List<Integer> ans = freqMap.pollLastEntry().getValue(); Get Entry's values will be a List
  • Map.Entry<Integer, LinkedList<Integer>> entry = freqMap.pollLastEntry(); --> Deal with all Entries

public int[] findFrequentTreeSum(TreeNode root) {
    if (root == null) return new int[0];
    Map<Integer, Integer> map = new HashMap<>();
    helper(map, root);
    // Map<Integer, LinkedList<Integer>> freqMap = new TreeMap<>();
    TreeMap<Integer, List<Integer>> freqMap = new TreeMap<>();
    for (Integer i : map.keySet()) {
        if (!freqMap.containsKey(map.get(i))) freqMap.put(map.get(i), new LinkedList<Integer>());
        freqMap.get(map.get(i)).add(i);
    }
    // Map.Entry<Integer, LinkedList<Integer>> entry = freqMap.pollLastEntry();
    List<Integer> ans = freqMap.pollLastEntry().getValue();
    // int[] res = new int[entry.getValue().size()];
    // for (int i = 0; i < res.length && entry.getValue().hasNext(); i++) {
    //     res[i] = entry.getValue().next();
    // }

    int[] res = new int[ans.size()];
    int index = 0;
    for (Integer i : ans) res[index++] = i;
    return res;
}
private int helper(Map<Integer, Integer> map, TreeNode root) {
    if (root == null) return 0;
    int sum = root.val + helper(map, root.left) + helper(map, root.right);
    map.put(sum, map.getOrDefault(sum, 0) + 1);
    return sum;
}