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.

For example:
Given the below binary tree,

1
/ \
2 3
Return 6.

这道题不难,主要是把思路想清楚即可
因为start和end可以是任何一点,所以对于任何一个node所有有可能这个max在左边子树,右边子树,或者跨过node本身,我们可以用recursive的办法来求出某个node左子树和右子树的最大path sum,但是还需要一个变量currMax来跟踪当前所有通过node连接左右的path最大值。currMax随着recursion的进行也要进行更新。

另外要注意的是如果是null的话,应该return一个Integer.MIN_VALUE而不应该return0,防止其他两个值都是负数的情况。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int currMax = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        return Math.max(findMaxPath(root), currMax);
        
    }
    
    public int findMaxPath(TreeNode root) // can not treat null as 0 because might be all negative
    {
        if (root == null)
            return Integer.MIN_VALUE;
        int left = findMaxPath(root.left);
        int right = findMaxPath(root.right);
        
        int branchMax = Math.max(left, right);
        branchMax = Math.max(branchMax, 0);
        branchMax += root.val;
        int tMax = root.val;
        tMax += Math.max(left,0);
        tMax += Math.max(right, 0);
        currMax = Math.max(currMax, tMax);
        return branchMax;
    }
}

Second Submission:
The Key to this problem is that recursion only returns the left/right branch, but use a separate global variable max to record the max across the root

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        findSubTree(root);
        return max;
    }
    
    public int findSubTree(TreeNode root) {
        if (root == null)
            return Integer.MIN_VALUE;
        int leftBranch = Math.max(findSubTree(root.left), 0);
        int rightBranch = Math.max(findSubTree(root.right), 0);
        int branch = root.val + Math.max(leftBranch, rightBranch); // recursion only return one branch
        int whole = root.val + leftBranch + rightBranch;
        max = Math.max(max, whole);
        return branch;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s