递进 124. Binary Tree Maximum Path Sum 【H】any node any node / D&C经典
https://leetcode.com/problems/binary-tree-maximum-path-sum/
http://www.jiuzhang.com/solutions/binary-tree-maximum-path-sum/
九章正统写法ResultType 2.80% 6ms 为什么很低
class ResultType {
int root2any, any2any;
ResultType(int root2any, int any2any) {
this.root2any = root2any;
this.any2any = any2any;
}
}
public class Solution {
public int maxPathSum(TreeNode root) {
ResultType result = helper(root);
return result.any2any;
}
public ResultType helper(TreeNode root) {
if (root == null)
return new ResultType(Integer.MIN_VALUE, Integer.MIN_VALUE);qiu
ResultType left = helper(root.left);
ResultType right = helper(root.right);
int root2any = Math.max(0, Math.max(left.root2any, right.root2any)) + root.val;
int any2any = Math.max(left.any2any, right.any2any);
any2any = Math.max(any2any, Math.max(0, left.root2any)
Math.max(0, right.root2any)
root.val);
return new ResultType(root2any, any2any);
}
}
**总结：
如果求any to any node的最大值：首先有三种情况，1. 一系列node都在左子树，2. 都在右子树；3. 跨过root的连续node。。。右图是求横跨root的情况，等于 左子树的root to any加上右子树的root to any 加上root.val。。所以整体思路就是：先求root to any，再比较any to any 取左右any to any最大的一个，再与中间的比较。
https://discuss.leetcode.com/topic/4407/accepted-short-solution-in-java/2
Discussion: 神方法：
public class Solution {
int maxValue;
public int maxPathSum(TreeNode root) {
maxValue = Integer.MIN_VALUE;
maxPathDown(root);
return maxValue;
}
public int maxPathDown(TreeNode root) {
if (root == null)
return 0;
int left = Math.max(0, maxPathDown(root.left));
int right = Math.max(0, maxPathDown(root.right));
maxValue = Math.max(maxValue, left + right + root.val);
return Math.max(left, right) + root.val;
}
}
**思路：没有看懂 maxPathDown 和 maxValue的关系是什么？
A path from start to end, goes up on the tree for 0 or more steps, then goes down for 0 or more steps. Once it goes down, it can't go up. Each path has a highest node, which is also the lowest common ancestor of all other nodes on the path.
A recursive method maxPathDown(TreeNode node) (1) computes the maximum path sum with highest node is the input node, update maximum if necessary (2) returns the maximum sum of the path that can be extended to input node's parent.