Binary Tree Maximum Path Sum

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 does not need to go through the root.

For example: Given the below binary tree,

   1
  / \
 2   3

Return 6.

Notes:

1. Use ResultType to keep two values: max and maxRootToNode
2. max is the maximum path sum
3. maxRootToNode is the maximum path sum from the root to any child node, must be bigger than 0 (ignore the ones which is lower than 0)
4. compare leftMax, rightMax and leftMaxRootToNode + root.val + rightMaxRootToNode to get the rootMax
5. compare leftMaxRootToNode and rightMaxRootToNode, add the root.val to get the rootMaxRootToNode.

    private class ResultType {
        public int rootToNodeMax;
        public int max;

        public ResultType() {
        }

        public ResultType(int rootToNodeMax, int max) {
            this.rootToNodeMax = rootToNodeMax;
            this.max = max;
        }
    }

    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }

        ResultType result = helper(root);
        return result.max;
    }

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

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

        ResultType leftResult = helper(root.left);
        ResultType rightResult = helper(root.right);

        int left = Math.max(0, leftResult.rootToNodeMax);
        int right = Math.max(0, rightResult.rootToNodeMax);
        int value = left + root.val + right;

        ResultType result = new ResultType();
        result.rootToNodeMax = Math.max(left, right) + root.val;
        result.max = Math.max(Math.max(leftResult.max, rightResult.max), value);

        return result;
    }