124.Binary Tree Maximum Path Sum

题目大意：找出一个二叉树中的最大路径长度。这个路径是从一个叶子结点到另一个叶子结点的路径长度。例子如下：

法一：DFS。由于是左边一个路径到右边一个路径，经过中间的根连接点，所得到的路径和，所以可以计算每个根节点的左子树和右子树的最大路径和，然后再从中选大者，再与其上一层进行比较。具体代码如下（耗时2ms）：

 1     //设为全局，方便计算，因为最大值有可能是中间路径，所以如果只是作为参数返回的话，不好承接
 2     int res = Integer.MIN_VALUE;
 3     public int maxPathSum(TreeNode root) {
 4         dfs(root);
 5         return res;
 6     }
 7     private int dfs(TreeNode root) {
 8         if(root == null) {
 9             return 0;
10         }
11         //计算左子树最大路径和
12         int left = Math.max(dfs(root.left), 0);
13         //计算右子树最大路径和
14         int right = Math.max(dfs(root.right), 0);
15         //求max
16         res = Math.max(res, left + right + root.val);
17         //取左子树和右子树的较大值，再加上当前根值返回给上一级
18         return Math.max(left, right) + root.val;
19     }

View Code