Binary Tree Maximum Path Sum

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:

1  / \ 2   3

Return 6.

1.解题思路

分析对于每一个根节点，可能的路径和有：左子树的最大路径和+该节点val，右子树的最大路径和+该节点val,只取该节点val,左子树的最大路径和+该节点val+右子树的最大路径和，我们需要取四个中最大的一个即可。但是本题的难点在于，使用递归实现，但是前面的第四种情况不能作为递归函数的返回值，所以我们需要定义两个max值，singleMax代表单边路径的最大值，用于递归；curMax用于singleMax和回路Max的较大值。

2.代码

public class Solution {    int max=Integer.MIN_VALUE;    public int maxPathSum(TreeNode root) {        helper(root);        return max;    }    private int helper(TreeNode root){        if(root==null) return 0;        int leftsum=helper(root.left);        int rightsum=helper(root.right);        int singlemax=Math.max(Math.max(leftsum+root.val,rightsum+root.val),root.val);        int curmax =Math.max(singlemax,leftsum+root.val+rightsum);        max=Math.max(max,curmax);        return singlemax;    }}