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

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型
 */
function maxPathSum( root ) {
    // write code here
    let maxSum = Number.MIN_SAFE_INTEGER;
    function maxPathSumRes(node) {
        if (node == null) {
            return 0;
        }
        let leftTree = Math.max(maxPathSumRes(node.left), 0);
        let rightTree = Math.max(maxPathSumRes(node.right), 0);
        const sum = node.val + leftTree + rightTree;
        maxSum = Math.max(maxSum, sum);
        return node.val + Math.max(leftTree, rightTree);
    }
    maxPathSumRes(root);
    return maxSum;
}
module.exports = {
    maxPathSum : maxPathSum
};

每次递归查找的时候更新最大值。

每次统计左子树+根+右子树，（注意：子树返回负数则不考虑）

返回其中一个子树+根当做一个最优路径。