124
Binary Tree Maximum Path Sum
21.6%
Hard
singlePathSum 必须经过自己
public class Solution {
int rst=Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
singlePathSum(root);
return rst;
}
private int singlePathSum(TreeNode p){
if (p == null) return 0;
int left = Math.max(0, singlePathSum(p.left));
int right = Math.max(0, singlePathSum(p.right));
rst = Math.max(rst, p.val + left + right);
return p.val + Math.max(left, right);
}
}
