124. Binary Tree Maximum Path Sum

Binary Tree Maximum Path

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.

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
      public int maxPathSum(TreeNode root) {
        if (root == null) return 0;

        Result result = maxPathHelper(root);
        return result.maxPath;
    }

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

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


        // left.maxPath, right.maxPath, left.rootPath + right.rootPath+root.val
        // left.rootPath + root.val, right.rootPath+root.val, root.val, 0

        int tmep = left.rootPath + right.rootPath + root.val;
        int maxPath = Math.max(Math.max(left.maxPath, right.maxPath), tmep);
        int rootPath = Math.max(Math.max(Math.max(left.rootPath + root.val, right.rootPath + root.val), root.val), 0);
        return new Result(maxPath, rootPath);
    }

    private class Result {
        int maxPath;
        int rootPath;

        public Result(int max, int rootPath) {
            this.maxPath = max;
            this.rootPath = rootPath;
        }
    }
}