题目及测试
package pid124;/*二叉树中的最大路径和给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。示例 1:输入: [1,2,3]1/ \2 3输出: 6示例 2:输入: [-10,9,20,null,null,15,7]-10/ \9 20/ \15 7输出: 42}*/
public class main {public static void main(String[] args) {Object[] x=new Object[]{-10,9,20,null,null,15,7}; BinaryTree tree=new BinaryTree(x);tree.printTree(tree.root);test(tree.root);}private static void test(TreeNode ito) {Solution solution = new Solution();int rtn;long begin = System.currentTimeMillis();rtn = solution.maxPathSum(ito);//执行程序long end = System.currentTimeMillis(); System.out.println("rtn=" );System.out.print(rtn);System.out.println();System.out.println("耗时：" + (end - begin) + "ms");System.out.println("-------------------");}}
没想出来
解法1（别人的）
初始化 max_sum 为最小可能的整数并调用函数 max_gain(node = root)。
实现 max_gain(node) 检查是继续旧路径还是开始新路径：
边界情况：如果节点为空，那么最大权值是 0 。
对该节点的所有孩子递归调用 max_gain，计算从左右子树的最大权值：left_gain = max(max_gain(node.left), 0) 和 right_gain = max(max_gain(node.right), 0)。
检查是维护旧路径还是创建新路径。创建新路径的权值是：price_newpath = node.val + left_gain + right_gain，当新路径更好的时候更新 max_sum。
对于递归返回的到当前节点的一条最大路径，计算结果为：node.val + max(left_gain, right_gain)。
即max_gain（node）方法，会返回node节点-它的某一侧的节点的最大长度。
某一侧节点-node-另一侧节点，这种情况的路径，会在方法内部更新max_sum字段，更新最大长度。
class Solution {int max_sum = Integer.MIN_VALUE;public int max_gain(TreeNode node) {if (node == null) return 0;// max sum on the left and right sub-trees of nodeint left_gain = Math.max(max_gain(node.left), 0);int right_gain = Math.max(max_gain(node.right), 0);// the price to start a new path where `node` is a highest nodeint price_newpath = node.val + left_gain + right_gain;// update max_sum if it's better to start a new pathmax_sum = Math.max(max_sum, price_newpath);// for recursion :// return the max gain if continue the same pathreturn node.val + Math.max(left_gain, right_gain);}public int maxPathSum(TreeNode root) {max_gain(root);return max_sum;}
}