下一个目标是弄清楚：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.
