面试热题（二叉树的最大路径）

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给定一个二叉树的根节点 root ，返回其 最大路径和，即所有路径上节点值之和的最大值。

 输入：root = [1,2,3] 输出：6 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

 这道题作为二叉树中的困难题，其实做起来也没有那么困难

       考虑题目定义的路径的一般情形：一条路从下向上延伸，到达一个最高节点后又向下延伸，将最高点节点称为拐点，但是拐点左侧或者右侧可能没有这个节点，我们需要考虑每个节点node作为拐点，都将有一个以其拐点的最大路径之和，并由下面式子得到：

leftRree+rightTree+root.val

       这里的leftTree/rightTree作为root的左右节点为该路径和带来的贡献，分别是拐点左半侧路径和拐点右半侧路径和，这道题求解过程就是考察当所有的节点作为拐点时该式的结果，最后取最大值，显然该式具有后续遍历dfs的特点（左右中），dfs()方法的参数为当前节点root,返回root作为拐点儿子的半侧路径和：

• 基准情形为递归到null时返回0
• 递归得到调用dfs分别求左右儿子的leftTree和rightTree
• 得到leftTree/rightTree后，以该式计算当前节点为拐点的最大路径max
• 更新全局最大路径和max
• 返回值是当前节点root作为拐点儿子的贡献值，容易有如下：

return root.val+Math.max(leftTree,rightTree);

即root将与其左右半侧路径中的较大者构成对上层拐点而言的更长的半侧路径

• 当dfs结束后，max中的值就是正确结果 

 注意：由于树中的节点可能都是负数，所以在取贡献的时候，如果为负数直接取0，表示该节点所在的侧路径不参与组成最大路径

源码：

    //维护一个全局变量int max=Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {//对入参进行判断if(root==null){return 0;}dfs(root);return max;}public int dfs(TreeNode root){//递归结束条件if(root==null){return 0;}int leftTree=Math.max(dfs(root.left),0);int rightTree=Math.max(dfs(root.right),0);int all=leftTree+rightTree+root.val;//更新最大值max=Math.max(max,all);return root.val+Math.max(leftTree,rightTree);}