题目描述

给定一个二叉树，请计算节点值之和最大的路径的节点值之和是多少。
这个路径的开始节点和结束节点可以是二叉树中的任意节点
例如：
给出以下的二叉树，
1↵ / ↵ 2 3
返回的结果为6

思路：
其实这种题我一直有个误区，这种递归题目不要去想内部递归是如何实现的，应该要想的是如何调用递归以及递归得到什么东西，比如这题，你要返回路径最大值，路径的开始节点和结束节点可以是二叉树中的任意节点，
那么对于一个二叉树是完全可以使用递归的，自低向上对应10和11行，首先自低向上分析每一个节点对应的左右的可能的最大值也就是 Math.max(Math.max(0, left)+root.val,Math.max(0, right)+root.val);也是这个递归函数的目的.对应13行。但13行并不是我们要的结果我们要的是最大值，所以我们就不断更新当前节点和当前节点左，右值的和，对应12行。13行返回给10和11行，然后12行又不断调用10和11行来更新自己。

代码一

  1. public static int res = Integer.MIN_VALUE;
  2.     public static int maxPathSum (TreeNode root) {
  3.         if(root==null)return 0;
  4.         preOrder(root);
  5.         return res;
  6.         // write code here
  7.     }
  8.     public static int preOrder(TreeNode root) {
  9.         if(root==null)return 0;
  10.         int left = preOrder(root.left);
  11.         int right = preOrder(root.right);
  12.         res = Math.max(res, Math.max(0, left)+root.val+Math.max(0, right));
  13.         return Math.max(Math.max(0, left)+root.val,Math.max(0, right)+root.val);
  14.     }