Leetcode: Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / 
     2   3
Return 6.

难度：75. 

参见了他人的思路，这道题是求树的路径和的题目，不过和平常不同的是这里的路径不仅可以从根到某一个结点，而且路径可以从左子树某一个结点，然后到达右子树的结点，就像题目中所说的可以起始和终结于任何结点。函数的返回值定义为以自己为根的一条从根到叶子结点的最长路径，这个返回值是为了提供给它的父结点计算自身的最长路径用。这样一来，一个结点自身的最长路径就是它的左子树返回值（如果大于0的话），加上右子树的返回值（如果大于0的话），再加上自己的值。在过程中求得当前最长路径时比较一下是不是目前最长的，如果是则更新。算法的本质还是一次树的遍历，所以复杂度是O(n)。而空间上仍然是栈大小O(logn)。注意这里path的存值方式是个问题，如果用一个integer变量代入recursion的话，函数无法对实参造成改变，所以用了一个对象ArrayList<Integer> res的第一个元素来存最大的path值

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxPathSum(TreeNode root) {
        if (root == null) return 0;
        ArrayList<Integer> res = new ArrayList<Integer>();
        res.add(Integer.MIN_VALUE);
        FindMaxSum(root, res);
        return res.get(0);
    }
    
    public int FindMaxSum(TreeNode root, ArrayList<Integer> res) {
        if (root == null) {
            return 0;
        }
        int leftsum = FindMaxSum(root.left, res);
        int rightsum = FindMaxSum(root.right, res);
        int maxsum = root.val + (leftsum>0? leftsum : 0) + (rightsum>0? rightsum : 0);
        if (maxsum > res.get(0)) res.set(0, maxsum);
        return root.val + Math.max(leftsum, Math.max(rightsum, 0));
    }
}

 Or we can use external variable

class Solution {
    int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        helper(root);
        return maxSum;
    }
    
    public int helper(TreeNode node) {
        if (node == null) return 0;
        int left = helper(node.left);
        int right = helper(node.right);
        maxSum = Math.max(maxSum, node.val + (left > 0 ? left : 0) + (right > 0 ? right : 0));
        return node.val + Math.max(0, Math.max(left, right));
    }
}