Problem

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,

       1
      / \
     2   3
Return 6.

思路

1. 首先开始想左子树和右子树分别返回anyToany的最大值, 和父节点的anyToAny有什么关系, 发现我们需要当前节点到某个节点的max path sum, 也就是curToAny. 所以返回的信息有两个
2. 节点的值可能为负数, 所以需要和零比较才组合成curToAny 以及 anyToAny

    public int maxPathSum(TreeNode root) {
        return helper(root).maxFromAny;
    }

    private Result helper(TreeNode root) {
        if (root == null) {
            return new Result(Integer.MIN_VALUE, Integer.MIN_VALUE);
        }

        if (root.left == null && root.right == null) {
            return new Result(root.val, root.val);
        }

        Result left = helper(root.left);
        Result right = helper(root.right);

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

        return new Result(maxFromAny, maxFromNode);
    }

    class Result {
        int maxFromAny;
        int maxFromNode;

        public Result (int maxFromAny, int maxFromNode) {
            this.maxFromAny = maxFromAny;
            this.maxFromNode = maxFromNode;
        }
    }