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

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型
 */
function maxPathSum( root ) {
    // write code here
    let max = -Infinity
    const maxGain = (node) => {
        if(node == null) return 0
        let left = Math.max(maxGain(node.left),0)
        let right =Math.max(maxGain(node.right),0)
		//如果以这个节点作为最大路径的联通点（也就是说从左节点到这个节点，再到右节点）那么此时可以组成的最大	  		//路径就是左孩子+右孩子+节点本身
        let nodeVal = node.val + left +right
        max =Math.max(nodeVal,max)
		//这里的情况是说：将该节点提供作为其他路径中的一环，那么它能提供的最大值只能选取左右孩子中的最大值
        return Math.max(left,right)+node.val

    }
    maxGain(root)
    return max
}
module.exports = {
    maxPathSum : maxPathSum
};