Bottom-Up

• 有些题目是必须自底向上才能做出来的，比如balances binary tree

• 一般这种题目都是helper method在recursive call的同时也返回了其它更有用的信息

• 本质上是建立了一个Tuple

• 不会Bottom-Up很多时候就是因为不会postOrder Traversal

• count univalue subtrees

• largest BST Subtree

Count Univalue Subtrees

• 建立一个global variable,在判断isUnival的同时计算cnt

• 核心是postOrder Traversal的思想

public class Solution {
    int cnt;
    public int countUnivalSubtrees(TreeNode root) {
        cnt = 0;
        isUnival(root);
        return cnt;
    }
    private boolean isUnival(TreeNode root){
        if(root == null) return true;
        boolean left = isUnival(root.left);
        boolean right =isUnival(root.right);
        if(left && right){
            if(root.left != null && root.left.val != root.val){
                return false;
            }
            if(root.right != null && root.right.val != root.val){
                return false;
            }
            cnt++;
            return true;
        }
        return false;
    }
}

Largest BST Subtree

• 建tuple!建tuple!建tuple!

• tuple里不需要记录val,也不需要left，right

public class Solution {
    public class Tuple{
        boolean isBST;
        int bstSize;
        int min;
        int max;
        public Tuple(){
            max = Integer.MIN_VALUE;
            min = Integer.MAX_VALUE;
            isBST = true;
            bstSize = 0;
        }
    }
    public int largestBSTSubtree(TreeNode root) {
        if(root == null) return 0;
        Tuple tuple = helper(root);
        return tuple.bstSize;
    }
    private Tuple helper(TreeNode root){
        if(root == null) return new Tuple();
        Tuple tuple = new Tuple();
        Tuple left = helper(root.left);
        Tuple right = helper(root.right);
        //postOrder
        if(!left.isBST || !right.isBST || left.max > root.val || right.min < root.val){
            tuple.isBST = false;
            tuple.bstSize = Math.max(left.bstSize, right.bstSize);
        }else{
            tuple.bstSize = 1 + left.bstSize + right.bstSize;
            tuple.min = root.left != null ? left.min : root.val;
            tuple.max = root.right != null ? right.max : root.val;
        }
        return tuple;
    }
}

Binary Tree Longest Consecutive Sequence

• 一言不合就建tuple咯

public class Solution {
    public class Tuple{
        int curLen;
        int maxLen;
        //TreeNode root;
        int val;
        public Tuple(TreeNode root){
            //this.root = root;
            this.val = root.val;
            curLen = 1;
            maxLen = 1;
        }
        public int maxLength(){
            return Math.max(curLen, maxLen);
        }
    }
    public int longestConsecutive(TreeNode root) {
        if(root == null) return 0;
        Tuple tuple = helper(root);
        return tuple.maxLen;
    }
    private Tuple helper(TreeNode root){
        if(root == null) return null;
        Tuple left = helper(root.left);
        Tuple right = helper(root.right);
        Tuple tuple = new Tuple(root);
        int leftLen = 0, rightLen = 0;
        if(left != null && left.val == root.val+1){
            leftLen = left.curLen;
        }
        if(right != null && right.val == root.val+1){
            rightLen = right.curLen;
        }
        tuple.curLen = Math.max(leftLen, rightLen) + 1;
        int subMax = 0;
        if(left != null) subMax = Math.max(subMax, left.maxLen);
        if(right != null) subMax  = Math.max(subMax, right.maxLen);
        tuple.maxLen = Math.max(tuple.curLen, subMax);
        return tuple;
    }
}