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

/*
 * 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 = -Infinity;

  function maxGain(node) {
    if (!node) return 0;

    // 递归计算左右子节点的最大贡献值
    const leftGain = Math.max(maxGain(node.left), 0);
    const rightGain = Math.max(maxGain(node.right), 0);

    // 当前节点的最大路径和
    const currentPathSum = node.val + leftGain + rightGain;

    // 更新全局最大路径和
    maxSum = Math.max(maxSum, currentPathSum);

    // 返回节点的最大贡献值
    return node.val + Math.max(leftGain, rightGain);
  }

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