124. Binary Tree Maximum Path Sum

Leetcode link

题目简介

/**
 * @param {TreeNode} root
 * @return {number}
 */

题目给我们一颗二叉树的根节点 root，要求我们找出二叉树中的一条路径使得该路径所有节点之和最大

路径的定义：路径之间两两节点必须有边连接，且相同的节点不允许经过两次

举个例子：

a
|
b
| \
c  d

a->b->c，a->b->d，c->b->d 都是路径；a->b->c->d 不是路径（因为 c 跟 d 不存在边连接）

解题思路

求二叉树节点之和最大，我们优先考虑使用 DFS 来遍历该二叉树

当我们遍历到每一个节点的时候，我们有两件事需要做：

1. 我们需要计算以当前节点为根的子树所有路径之和最大的值是多少（对应到我们上述例子的 c->b->d 这种情况）
2. 我们需要计算如果当前节点能向上传递的最大路径之和是多少（对应 a->b->c，a->b->d 二选一的情况）

第一种情况，站在 b 的视角，我们要考虑的是 max(b, b+c, b+d, b+c+d c, d)

第二种情况，站在 b 的视角，我们要考虑的是 max(b, b+c, b+d)

对于每次 dfs ，我们都要用变量记录第一种情况；返回第二种情况

Javascript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxPathSum = function (root) {
    let max = root.val

    const dfs = (node, sum) => {
        if (!node) {
            return sum
        }

        const leftBranchSum = dfs(node.left, sum)
        const rightBranchSum = dfs(node.right, sum)
        const maxSingleBranchSum = Math.max(leftBranchSum + node.val, rightBranchSum + node.val, node.val)
        max = Math.max(max, leftBranchSum + rightBranchSum + node.val, maxSingleBranchSum)

        return maxSingleBranchSum
    }

    dfs(root, 0)

    return max
};