# 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;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://syjohnson11.gitbook.io/leetcode/4_binary_tree/bottom-up.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.