Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
Example 1:
Input: [1,2,3]
1
/ \
2 3
Output: 6
Example 2:
Input: [-10,9,20,null,null,15,7] -10
/ \
9 20
/ \
15 7 Output: 42
思路
dfs:
2
/ \
1 -3
maxPath: 1 + 2 + 0
1. use maxPath to update result from all paths which is max path sum
2. divide a path into 3 parts:
a. left path: from root to left side down to 0 or more steps
b. right path: from root to right side down to 0 or more steps
c. cur root itself
3. maxPath = c + (a>0 ? a: 0 ) + (b > 0 ? b:0)
这是一道关于BST和recursion的经典题，需要掌握
最naive的想法是找到所有BST的path，返回max
发现， 任意一条path都有一个顶点（位置最高点）
我们用这个顶点来分解所有path
这样，以任意一个点为顶点的path就分解为
a. max_sum (左边path)
b. max_sum (右边path)
c. 顶点自己的value
进一步，
a + b + c 组成的人字形path的max path sum
2
/ \
1 -3
dfs的return value : 2(顶点自己的value必须加上，无论正负) + 1 （正数贡献自己） + 0 (-3为负数不做贡献就是及时止损了) = 3
跟 [leetcode]543. Diameter of Binary Tree二叉树直径 的思路基本一致。
代码
class Solution {
public int maxPathSum(TreeNode root) {
// corner case
if(root == null){return 0;}
/* 要么用个global variable放在class下，要么用长度为1的一维数组来存。
maxSum的value，可正可负，初始化为Integer.MIN_VALUE。
*/
int[] maxPath = new int[]{Integer.MIN_VALUE};
dfs(root, maxPath);
return maxPath[0];
}
// 递归求以root为顶点所有直上直下的path中，path sum最大的一条值。没有U-turn的
private int dfs(TreeNode root, int[]maxPath){
// left > 0 benefit sum, add to sum; left < 0 will worsen sum, default 0
int left = root.left != null ? Math.max(dfs(root.left, maxPath), 0) : 0;
int right = root.right != null ? Math.max(dfs(root.right, maxPath), 0) : 0;
int cur = root.val + left + right;
maxPath[0] = Math.max(maxPath[0], cur);
return root.val + Math.max(left, right);
}
}