> For the complete documentation index, see [llms.txt](https://syjohnson11.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://syjohnson11.gitbook.io/leetcode/4_binary_tree/bottom-up.md).

# Bottom-Up

* 有些题目是必须自底向上才能做出来的，比如balances binary tree
* 一般这种题目都是helper method在recursive call的同时也返回了其它更有用的信息
* **本质上是建立了一个Tuple**
* **不会Bottom-Up很多时候就是因为不会postOrder Traversal**
* count univalue subtrees
* largest BST Subtree

### [Count Univalue Subtrees](https://leetcode.com/problems/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](https://leetcode.com/problems/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](https://leetcode.com/problems/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;
    }
}
```