LeetCode(61) -- 124

P124. Binary Tree Maximum Path Sum (Hard)

一个二叉树，找出所有路径中所有的数的和最大的值是多少。

我的思路

对于每一个节点，虽然在左右子节点各自的内部构成的最长路径并不知道，但是，我可以知道通过这个节点可以构成的新的一条路径。因为节点可以是负数，所以这条新路径它可能只包含本身，也可以是自身和左子节点，也可以是自身和右子节点，也可能是左子节点加自身再加右子节点。因此，每个节点向下能达到的最大值就很重要。所以我的递归函数，返回了每个节点一直向下到最底层可以累加的最大值。然后通过一个全局变量来记录历史上出现过的最大值。

我的代码

class Solution {
    int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        oneWaySum(root);
        return max;
    }

    private int oneWaySum(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = oneWaySum(node.left);
        int right = oneWaySum(node.right);
        max = Math.max(max, node.val);
        max = Math.max(max, node.val + left);
        max = Math.max(max, node.val + right);
        max = Math.max(max, left + right + node.val);
        return Math.max(node.val, node.val + Math.max(left, right));
    }
}

99%

最优解

class Solution {
    int MaxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        Helper(root);
        return MaxSum;
    }

    private int Helper(TreeNode root) {
        if(root == null)
            return 0;
        int left = Math.max(0, Helper(root.left));
        int right = Math.max(0, Helper(root.right));
        MaxSum = Math.max(MaxSum, left + right + root.val);
        return Math.max(left, right) + root.val;
    }
}

思路基本差不多，只不过把左和右分别跟0比较了一下，这样就排除了负数的干扰。值得学习。