二叉树中的最大路径和

• 二叉树中的最大路径和
  • 题目详情
  • 解题思路
  • 代码实现

题目详情

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。 路径和 是路径中各节点值的总和。 给你一个二叉树的根节点 root ，返回其 最大路径和

解题思路

感觉现在找最深或者什么路径的总和，第一反应就是深度优先搜索，所以这里使用深度优先搜索（DFS）和递归来解决。 需要计算：

1. 通过该节点的最大路径和，这可能包括左子树和右子树。
2. 不通过该节点的最大路径和，这可能是左子树的最大路径和或右子树的最大路径和。
3. 可以更新全局最大路径和，并返回不通过该节点的最大路径和。

代码实现

var maxPathSum = function(root) {
  let maxSum = Number.MIN_SAFE_INTEGER

  var maxGain = function(node) {
    if (node === null) return 0;
    let leftGain = Math.max(maxGain(node.left), 0)
    let rightGain = Math.max(maxGain(node.right), 0)
    let newPath = node.val + leftGain + rightGain
    maxSum = Math.max(maxSum, newPath)
    return node.val + Math.max(leftGain, rightGain)
  }
  maxGain(root)//从根节点进行深度优先搜索
  return maxSum
};