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.

Example:

Given the below binary tree:

  1
 / \
2   3

return 6.

Solution:

This is an improved version of Binary Tree Maximum Path Sum II. Consider the example above, we have following cases:

1. Maximum between left subtree (2) and right subtree (3)
2. Maximum between left subtree (2) and right subtree (3) with current node (1)
3. Path from any node in left subtree (2) to current node (1) then to any node in right subtree

Code:

class ResultType {
    int any2any;
    int root2any;
    public ResultType(int inAny2any, int inRoot2any) {
        any2any = inAny2any;
        root2any = inRoot2any;
    }
}
public class Solution {

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

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

        ResultType left = helper(root.left);
        ResultType right = helper(root.right);
        int left2any = Math.max(left.root2any, 0);
        int right2any = Math.max(right.root2any, 0);

        int root2any = Math.max(left2any, right2any) + root.val;

        int any2any = Math.max(left.any2any, right.any2any);
        any2any = Math.max(any2any, left2any + right2any + root.val);
        return new ResultType(any2any, root2any);
    }
}