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

For example:
Given the below binary tree,

       1
      / \
     2   3

Return6.

Solution)

Compare for the current value and left and right result. In addition, we need to keep the current max sum using a pointer.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int helper(TreeNode node, int[] res) {
        if (node == null) return 0;
        int left = Math.max(0, helper(node.left, res));
        int right = Math.max(0, helper(node.right, res));
        res[0] = Math.max(res[0], left + right + node.val);
        return Math.max(left, right) + node.val;
    }

    public int maxPathSum(TreeNode root) {
        int[] res = {Integer.MIN_VALUE};
        helper(root, res);
        return res[0];
    }
}