Given a binary tree, find the maximum path sum.

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

Example

Given the below binary tree:

1
 / \
2   3

return6.

1 计算左右两边single path sum （single path sum计算从root出发到任一结点的sum, 可能不含任何元素），然后和max比较 （思路取自九章算法）

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: An integer.
     */
    public class ReturnType {
        int singlePathSum, maxPathSum;
        public ReturnType(int singlePath, int maxPath) {
            this.singlePathSum = singlePath;
            this.maxPathSum = maxPath;
        }
    }
    public int maxPathSum(TreeNode root) {
        // write your code here
        if (root == null) {
            return 0;
        }

        ReturnType ans = maxPathSumHelper(root);
        return ans.maxPathSum;
    }

    public ReturnType maxPathSumHelper(TreeNode root) {
        if (root == null) {
            return new ReturnType(0, Integer.MIN_VALUE);
        }

        ReturnType left = maxPathSumHelper(root.left);
        ReturnType right = maxPathSumHelper(root.right);

        int singlePathSum = Math.max(0, Math.max(left.singlePathSum + root.val, right.singlePathSum + root.val));

        int maxSum = Math.max(left.maxPathSum, right.maxPathSum);
        maxSum = Math.max(maxSum, left.singlePathSum + right.singlePathSum + root.val);

        return new ReturnType(singlePathSum, maxSum);

    }
}