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.
摘抄自（http://www.cnblogs.com/springfor/p/3886411.html）题解：
“递归求解。
取当前点和左右边加和，当前点的值中最大的作为本层返回值。并在全局维护一个max。使用数组，因为是引用类型。所以在递归过程中可以保存结果。”
这里要想好比较的是什么，当前值val, 当前值+左路，当前值+右路，当前值+左右路，历史最大值
public class Solution { public int maxPathSum(TreeNode root) { int[] res = new int[1]; res[0] = Integer.MIN_VALUE; //!!!!!!!! 否则就默认了 0 ，一旦数组都是负数呢 findMax(res,root); return res[0]; } private int findMax(int[] res, TreeNode n){ if(n==null) return 0; int L = findMax(res, n.left); int R = findMax(res, n.right); int tmp= Math.max(n.val,Math.max(n.val+R,n.val+L)); res[0] = Math.max(res[0],Math.max(tmp,n.val+R+L)); return tmp; } }
原文：http://www.cnblogs.com/jiajiaxingxing/p/4565408.html