Friday, January 2, 2015

Binary Tree Maximum Path Sum Leetcode

public class Solution {
    int max;
    public int maxPathSum(TreeNode root) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
    if(root==null)  return 0;
    max = root.val;
    int currentmax = maxPathHelper(root);
    return (max>currentmax) ? max : currentmax;
}
public int maxPathHelper(TreeNode root)  {
    if(root==null)  return 0;
    int leftmax = maxPathHelper(root.left);
    int rightmax = maxPathHelper(root.right);
    max = Math.max(root.val+leftmax+rightmax,max);
    max = Math.max(root.val+leftmax,max);
    max = Math.max(root.val+rightmax,max);
    return Math.max(Math.max(leftmax,rightmax)+root.val,root.val);
}
}

No comments:

Post a Comment