124. Binary Tree Maximum Path Sum

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int maxValue=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        int r=postOrder(root);
        return Math.max(maxValue,r);
    }
    
    int postOrder(TreeNode root)
    {
        if(null==root)return Integer.MIN_VALUE;
        int left=postOrder(root.left);
        int right=postOrder(root.right);
        maxValue=Math.max(maxValue,root.val);
        int result=root.val;
        if(root.left!=null)
        {
            maxValue=Math.max(maxValue,left);
            result=Math.max(result,left+root.val);
        }
        
        if(root.right!=null)
        {
            maxValue=Math.max(maxValue,right);
            result=Math.max(result,root.val+right);
        }
        
        if(root.left!=null&&root.right!=null)
        {
            maxValue=Math.max(maxValue,left+root.val+right);
        }
        return result;
    }
}

Details 
Runtime: 1 ms, faster than 99.70% of Java online submissions for Binary Tree Maximum Path Sum.
Memory Usage: 39.5 MB, less than 94.25% of Java online submissions for Binary Tree Maximum Path Sum.

完全没看答案可算accept了, 事后看了眼答案, 果然厉害,不需要任何if判断.

https://leetcode.com/problems/binary-tree-maximum-path-sum/discuss/39775/Accepted-short-solution-in-Java

先记录我这个"辣鸡"版本的思路, 这个求二叉树的最长路径和, 最开始只想到暴力搜索.. 然后想到有个类似题 Binary Tree Tilt , 于是就做了.

思路完全是一样的, tilt是求绝对值, 这个是求和....就没搞懂怎么就一个是easy 一个是hard了....

当然这题的麻烦之处在于怎么处理null节点, 也就是边界问题.

按照标准答案对比了我的答案. 修改如下

class Solution {
    int maxValue=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        postOrder(root);
        return maxValue;
    }
    
    int postOrder(TreeNode root)
    {
        if(null==root)return 0;
        int left=Math.max(0,postOrder(root.left));
        int right=Math.max(0,postOrder(root.right));
        //maxValue=Math.max(maxValue,root.val); 
        //maxValue=Math.max(maxValue,left);
        //maxValue=Math.max(maxValue,right);
        maxValue=Math.max(maxValue,left+root.val+right);
    
        return Math.max(left,right)+root.val;
    }
}

if判断全部去掉.  当null==root时,必须返回一个值,用什么好呢,如果用MIN_VALUE, 则会出现两个MIN_VALUE相加而溢出...恶心.!

这里用了0, 并且同时用Math.max(0,postOrderxxx) 来防止全是负数的情况, 不然0就比负数大了.

中间三个判断全部不需要(注释部分),我们来想一下为什么, 假如中间三个任意一个成立, 那么第四个语句一定成立,因为他就是把三个值全加起来.  所以中间三句属于重复判断,没有意义

中间三个不可能出现全不成立的情况.  left/right/root  一共就这三部分,总会有个最大的.