【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.

For example:
Given the below binary tree,

       1
      / 
     2   3

Return 6.

题解：递归的思想，首先要明确一个点root为根的树中路径的最大值有四种情况：

只有根节点的路径；
从左子树值最大的路径->根节点；
从右子树值最大的路径->根节点；
从左子树值最大的路径->根节点->右子树值最大的路径；

要注意的一点就是递归函数返回的并不是最终的答案。如下图所示：

计算根节点root的最大值，调用递归函数计算左子树的最大路径值是3，如果直接把这个值返回就错了，因为root不通过它的左子-2就不能到达3，所以返回的值应该为经过root并以root为重点的路径的最大值，即root.val+max(left_max,right_max)；而真正的最大值用一个类变量maxx记录，在递归的过程中，这个值随时被更改并保持最大，它等于上述四种情况中最大的一种，在得到left_max和right_max的时候我就直接把它们和0比较取大的，所以不用单独考虑情况2，3了：

maxx =  Math.max(maxx,Math.max(root.val, root.val+left_max+right_max));

一个完整的例子如下图所示，其中花括号中第一个数为递归在该节点上返回的函数值，第二个数为当前maxx的值

代码如下：

 1 /**
 2  * Definition for binary tree
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11       private int maxx;
12       public int maxPathSum(TreeNode root) {
13           if(root == null)
14             return 0;
15           maxx = root.val;
16           Recur(root);
17           return maxx;
18       }
19       
20       public int Recur(TreeNode root){
21           if(root == null)
22               return 0;
23               
24           int left_max = Recur(root.left);
25           left_max = left_max > 0? left_max:0;
26           int right_max = Recur(root.right);
27           right_max = right_max > 0? right_max:0;
28           
29           maxx =  Math.max(maxx,Math.max(root.val, root.val+left_max+right_max));
30           return root.val+Math.max(left_max,right_max);
31       }
32 }

代码中第29行更行maxx；

30行返回从左子树（右子树）到根节点的路径最大值