题解 | #二叉树中的最大路径和#

采用后序遍历。当访问当前节点值的时候，统计并保存两个变量：以当前节点为一端的路径的最大路径和，全局最大路径和。

当访问当前节点值的时候，已知的值有： 当前全局最大路径和Max，以左子树根节点为一端的路径的最大路径和L，以右子树根节点为一端的路径的最大路径和R，当前节点值V。

求当前全局最大路径和Max，正常比较需要比较6次，①V与Max②Max与V+L③Max与V+R④Max与V+L+R⑤Max与L⑥Max与R。

但是由于采用的是递归，左右子树都已经跟Max比较过了，因此⑤和⑥是多余的。因此仅需要比较4次。

利用数学不等式分析发现，如果L、R都是正数，那么当前全局最大路径和Max = Max{Max,V+L+R}，①②③都是多余的。

如果L或者R为负数，那么相应的②或者③是不必要的。也就是说，当L或者R为负数时，令L0=0，R0=0，分别取代L和R，代入④即可求取当前全局最大路径和Max——进而可以省略①②③。

【注：笔者原先采用的是6次比较的方式，参考了讨论区的代码，进一步分析后总结出上述内容。以下代码参考自@韩迅 】

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    int maxValue;
    public int maxPathSum(TreeNode root) {
        maxValue = Integer.MIN_VALUE;
        maxPathDown(root);
        return maxValue;
    }
    private int maxPathDown(TreeNode node){
        if(node==null)
            return 0;
        int left = Math.max(0, maxPathDown(node.left));
        int right = Math.max(0, maxPathDown(node.right));
        maxValue = Math.max(maxValue, left + right + node.val);
        return Math.max(left, right) + node.val;
    }
}