学步园

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.

思路

1 一看到这类题目，马上想到递归

2 想到递归，就从root，left，right的角度结合题目去考虑。

3 对于root，考虑最长路径

a 只在left这边

b 只在right这边

c 通过root，从left到right

4 从递归的角度，越下面的可以保存到这个root网上走的最大值，同时也需要保存计算到目前的最大值。

5 java 可以用传递数组或者全局变量来在递归的时候保存某个值。

代码

public class Solution {
    public int maxPathSum(TreeNode root) {
        if(root==null){
            return 0;
        }
        int[] max = {Integer.MIN_VALUE};
        useme(root,max);
        return max[0];
    }
    
    public int useme(TreeNode root,int[] max){
        if(root==null){
            return 0;
        }
        int leftmax = useme(root.left,max);
        int rightmax = useme(root.right,max);
        int temp1 = leftmax+ rightmax+root.val;
        int temp2 = Math.max(root.val, Math.max(leftmax, rightmax)+root.val);  
        max[0]=Math.max(Math.max(temp1,temp2),max[0]);
        return temp2;
    }
}