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

题目链接：https://leetcode.cn/problems/binary-tree-maximum-path-sum/

代码

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function maxPathSum(root: TreeNode | null): number {
    let max = -Infinity;
    function dfs(node: TreeNode | null): number {
        if (!node) return 0;
        const left = Math.max(0, dfs(node.left));
        const right = Math.max(0, dfs(node.right));
        max = Math.max(max, left + right + node.val);
        return Math.max(left, right) + node.val;
    }
    dfs(root);
    return max;
};

思路

使用深度优先搜索（DFS）遍历整棵树，并在递归过程中同时维护：

以当前节点为起点，向下延伸的最大贡献值
经过当前节点的路径和最大值，用来更新全局答案

对于每个节点：

递归计算左子树的最大贡献值 left
递归计算右子树的最大贡献值 right
如果某一侧贡献为负数，则舍弃，按 0 处理
当前节点作为路径拐点时，可形成路径和 left + right + node.val
用该值更新全局最大路径和
向父节点返回当前节点的最大单边贡献值 Math.max(left, right) + node.val

关键点

路径可以从任意节点开始，到任意节点结束，不要求经过根节点
返回给父节点的路径只能选择左子树或右子树中的一条，不能同时选两边
计算全局答案时，当前节点可以同时连接左右子树，形成一条完整路径
使用 Math.max(0, dfs(...)) 可以直接剪掉负贡献分支
时间复杂度： $O (n)$ ，其中 $n$ 是节点数，每个节点只访问一次
空间复杂度： $O (h)$ ，其中 $h$ 是树的高度，主要为递归栈开销

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

代码 ​

思路 ​

关键点 ​

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

代码

思路

关键点