124 Binary Tree Maximum Path Sum

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);
    }
}