Wednesday, September 25, 2013

Leetcode - Binary Tree Maximum Path Sum

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.


/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int res = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        if(root == null)    return 0;
        
        res = Integer.MIN_VALUE;
        
        getMaxSum(root);
        
        return res;
    }
    
    public int getMaxSum(TreeNode node) {
        if(node == null)    return 0;
        
        int left = getMaxSum(node.left);
        int right = getMaxSum(node.right);
        
        int thisSum = node.val;
        
        if(left > 0)    thisSum += left;
        if(right > 0)   thisSum += right;
        
        res = Math.max(res, thisSum);
        
        // only need return the largest subtree with this node val
        return node.val + Math.max(0, Math.max(left, right));
    }
}

No comments:

Post a Comment