124.二叉树中的最大路径和

二叉树中的最大路径和

给你一个二叉树的根节点 root，返回其最大路径和。路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。

解析

var maxPathSum = function (root) {
  let maxSum = -Infinity;
  function dfs(node) {
    if (!node) return 0;
    const left = Math.max(0, dfs(node.left));
    const right = Math.max(0, dfs(node.right));
    maxSum = Math.max(maxSum, node.val + left + right);
    return node.val + Math.max(left, right);
  }
  dfs(root);
  return maxSum;
};

对每个节点，左右子树贡献取 max(0, …)，避免负数拖累路径和。