Top down/Bottom up in Tree

下一个目标是弄清楚：Top down和Bottom up

理解：
Bottom up - 是指不到最下面的叶节点，不会return（触底后反弹 - 下面得到的值一层层带回去）

Top down

class Solution {
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        getNewGreaterVal(root);
        return root;
        
    }
    private void getNewGreaterVal(TreeNode cur) {
        if ( cur == null ) return; // 叶节点值不变
        getNewGreaterVal(cur.right);
        cur.val += sum;
        sum = cur.val; // 上一次是right child的值; 
        // sum 要作为global变量，因为需要在cur.right和 cur之间传递
        getNewGreaterVal(cur.left);
        
        
    }
}

注意private 函数返回类型是void！

124. Binary Tree Maximum Path Sum - bottom up approach

https://www.geeksforgeeks.org/find-maximum-path-sum-in-a-binary-tree/

class Solution {
    private int maxSum;
    public int maxPathSum(TreeNode root) {
        maxSum = Integer.MIN_VALUE;
        findMax(root); // bottom up
        return maxSum; // global value
    } 

    private int findMax(TreeNode p) {
        if (p == null) return 0;
        int left = findMax(p.left);
        int right = findMax(p.right);
        maxSum = Math.max(p.val + left + right, maxSum); 
        // when subtree.val is negative, first is p.val + 0 + 0,
        // then compare it with existed maxSum
        int ret = p.val + Math.max(left, right); // little trick here
        return ret > 0? ret: 0; 
    }
}

    * 注意
    
    1. nodes里会出现负值点，negative value. 
        全是负数时：返回最小的负数；
        如果有正数时，肯定不包括负数时 的maxSum最大。
    2. a little trick here: 
If this maximum happens to be negative, we should return 0, which means: “Do not include this subtree as part of the maximum path of the parent node”, which greatly simplifies our code.