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

For example:
Given the below binary tree,

       1
      / \
     2   3

Return6.

tag: binary tree, path

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private class Path{
        int goLeft;
        int goRight;

        public Path(int goLeft, int goRight){
            this.goLeft = goLeft;
            this.goRight = goRight;
        }
    }

    int ans = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        helper(root);

        return ans;
    }

    private int helper(TreeNode root){
        if (root == null){
            return 0;
        }

        int leftPath = helper(root.left);
        int rightPath = helper(root.right);

        ans = Math.max(ans, root.val + leftPath);
        ans = Math.max(ans, root.val + rightPath);
        ans = Math.max(ans, leftPath + rightPath + root.val);
        ans = Math.max(ans, root.val);

        // System.out.println("node val: " + root.val);
        // System.out.println("ans: " + ans);
        // System.out.println("return val: " + Math.max(root.val + leftPath, root.val + rightPath));
        // System.out.println("|||||||||||||||||||");

        return Math.max(root.val, Math.max(root.val + leftPath, root.val + rightPath));
    }
}