二叉树中的最大路径和 - Stellar Observer Protocol

717 字

4 分钟

二叉树中的最大路径和

2025-08-13

Algorithms

树

/

深度优先搜索

/

动态规划

/

二叉树

题目描述#

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

解题思路#

递归分治策略：
- 后序遍历二叉树（左→右→根）
- 对每个节点计算其作为路径根的最大路径和
- 返回该节点对父节点的最大贡献值
路径类型处理：
- 路径可能包含当前节点 + 左分支
- 路径可能包含当前节点 + 右分支
- 路径可能包含左分支 + 当前节点 + 右分支（全局路径）
贡献值传递：
- 节点对父节点的贡献 = 节点值 + max(左贡献, 右贡献)
- 负贡献值视为0（不选择该分支）
全局最大值更新：
- 每次计算包含当前节点的完整路径和
- 更新全局最大路径和

关键洞察#

路径组合多样性：
- 最大路径可能不经过根节点
- 需考虑所有可能的路径组合形式
贡献值概念：
- 节点贡献值只能包含单边分支（左或右）
- 完整路径计算需独立于贡献值传递
负值剪枝：
- 舍弃负贡献分支（贡献值取 max(0, 分支贡献)）
- 避免负值降低路径和
后序优势：
- 先获取子树信息再计算当前节点
- 自然支持复杂路径组合计算

复杂度分析#

指标	说明
时间复杂度	O(n)：每个节点访问一次
空间复杂度	O(h)：递归栈深度（h为树高，最坏O(n)）

代码实现#

1
/**
2
 * Definition for a binary tree node.
3
 * function TreeNode(val, left, right) {
4
 *     this.val = (val===undefined ? 0 : val)
5
 *     this.left = (left===undefined ? null : left)
6
 *     this.right = (right===undefined ? null : right)
7
 * }
8
 */
9
/**
10
 * @param {TreeNode} root
11
 * @return {number}
12
 */
13
var maxPathSum = function (root) {
14
    let result = -Infinity;
15

16
    const dfs = (root) => {
17
        if (!root) return 0;
18
        const left = Math.max(dfs(root.left), 0);
19
        const right = Math.max(dfs(root.right), 0);
20
        const max = left + right + root.val;
21
        result = Math.max(result, max);
22
        return Math.max(left, right) + root.val
23
    }
24

25
    dfs(root);
26

27
    return result;
28
};