LeetCode : 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.

**通常找max的題目, 元素中有負值的話，計算cost時，千萬不要把負值的部份也加進去。因為答案是可以選擇性不包括負值部份。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int calcmaxbranch(TreeNode root,HashMap<TreeNode,Integer> maxbranch)
    {
        if(root==null)return 0;
        int llen=calcmaxbranch(root.left,maxbranch);
        int rlen=calcmaxbranch(root.right,maxbranch);
        int ext=(llen>rlen)?llen:rlen;
        int mylen=root.val+(ext>0)?ext:0;
        maxbranch.put(root,mylen);
        return mylen;
    }
    public int findMaxPathSum(TreeNode root,HashMap<TreeNode,Integer> maxbranch)
    {
        if(root==null)return 0;
        int sum2=Integer.MIN_VALUE;
        int sum3=Integer.MIN_VALUE;
        int sum11=0;
        if(root.left!=null)
        {
            sum11=maxbranch.get(root.left);
            sum2=findMaxPathSum(root.left,maxbranch);
        }
        int sum12=0;
        if(root.right!=null)
        {
            sum12=maxbranch.get(root.right);
            sum3=findMaxPathSum(root.right,maxbranch);
        }
        int sum1=root.val;
        if(sum11>0)sum1+=sum11;
        if(sum12>0)sum1+=sum12;
        int max=sum1;
        if(sum2>max)max=sum2;
        if(sum3>max)max=sum3;
        return max;
    }
   
    public int maxPathSum(TreeNode root) {
        HashMap<TreeNode,Integer> maxbranch=new HashMap<TreeNode,Integer>();
        calcmaxbranch(root,maxbranch);
        int res=findMaxPathSum(root,maxbranch);
        return res;
    }
}