LeetCode LCR 051. 二叉树中的最大路径和

2026-03-28 HGNULB 约 8 分钟

文章信息 5 个分类 5 个标签

分类

LeetCode 困难 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 051. 二叉树中的最大路径和

题意分析

题目目标：在二叉树中找出一条节点序列，序列里相邻节点之间必须有边相连且每个节点至多出现一次，使这些节点的值之和最大，返回这个最大和。路径不必经过根，也不必以叶子为端点。
核心约束：路径可以"拐弯"——它可以从左子树的某个节点上行到某个节点再下行到右子树，但在任意一个节点处最多只能用到两条边，也就是说一条路径在最高点处至多合并左右两个下行分支。这个"至多两条边"的限制，是把全局问题拆成局部问题的钥匙。
边界处理：节点值可以是负数，路径至少包含一个节点，所以答案不能初始化为 0，也不能是空路径；全负树的答案是其中最大的那个单节点值；单节点树答案就是它本身。
实现取舍：每条路径都有唯一的最高点（深度最小的那个节点）。按最高点给所有路径分类，问题就变成"对每个节点，求以它为最高点的最优路径值"，再取全局最大。

解法：动态规划递推

核心思路

暴力做法是枚举路径的两个端点再求它们之间的路径和，端点组合是 $O(n^2)$ 级别，求和还要再走一遍路径，完全不可行。
关键观察是给路径找一个规范代表：任何一条路径都有唯一的最高点，且在最高点处这条路径由"向左的一条下行链"和"向右的一条下行链"拼成（其中任意一条可以为空）。而离开最高点之后，路径就只能一直向下，不能再拐弯。这两种形态必须分开定义，否则递归返回值的含义就会自相矛盾。
于是定义状态：dfs(node) 返回"从 node 出发一路向下所能取得的最大链和"，注意这是单臂值，只能选左右其中一边继续延伸。递推式是 dfs(node) = node.val + max(0, dfs(node.left), dfs(node.right))；取 0 的含义是——如果某一侧的最大链和为负，那就干脆不要这一侧，路径在这里截断。
与此同时，在每个节点处结算一次以它为最高点的最优路径：node.val + max(0, dfs(left)) + max(0, dfs(right))，这是允许拐弯的双臂值，用它去更新全局答案。返回单臂、结算双臂，两个量各司其职，这就是整道题的全部内容。
答案变量初始化为一个小于所有可能取值的数（题目值域为 $[-1000, 1000]$，故取 -1001），保证全负树时不会被 0 之类的伪值污染。

解题步骤

递归入口对空节点返回 0。为什么是 0：dfs 的返回值随后要被 Math.max(0, ...) 过滤，空子树贡献 0 与"不选这一侧"完全等价，语义自洽。

计算 left = Math.max(0, dfs(root.left)) 与 right = Math.max(0, dfs(root.right))。为什么要和 0 取大：节点值可以为负，一条负的下行链只会拖累总和，直接舍弃比强行拼接更优；这一步同时把"分支可以为空"这条规则编码进了数值里。

用 answer = Math.max(answer, root.val + left + right) 结算以当前节点为最高点的路径。为什么可以左右都加：当前节点是这条路径的最高点，它允许同时使用左右两条边，这正是"拐弯"发生的唯一位置。

返回 root.val + Math.max(left, right)。为什么返回值里只能选一侧：这个值要交给父亲继续往上拼接，若把左右都算上，父亲再接一条边就会让当前节点用到三条边，那不再是一条简单路径。

为什么结算与返回必须用两个不同的表达式：它们回答的是两个不同的问题——"以我为最高点的最优路径"和"从我出发向下的最优链"，混用其中任何一个都会得到错误答案。

答案变量初始化为 -1001 并在主函数中于递归结束后返回。为什么不能初始化为 0：全负树如 [-3] 的正确答案是 -3，若初值为 0 会返回 0，等价于允许了空路径。

以 具体用例：树 [-10, 9, 20, null, null, 15, 7] 走一遍。先到 9：左右均为空，left = right = 0，结算 9 + 0 + 0 = 9 使 answer = 9，返回 9 + 0 = 9。再到 15：同理结算 15，answer = 15，返回 15。到 7：结算 7，answer 仍是 15，返回 7。到 20：left = max(0, 15) = 15，right = max(0, 7) = 7，结算 20 + 15 + 7 = 42 使 answer = 42，返回 20 + max(15, 7) = 35。最后到根 -10：left = max(0, 9) = 9，right = max(0, 35) = 35，结算 -10 + 9 + 35 = 34，小于 42 所以 answer 保持 42，返回 -10 + 35 = 25。最终答案 42，对应路径 15 -> 20 -> 7，它的最高点正是 20。注意根处结算出的 34 之所以更差，是因为 -10 这个负值把两侧连了起来，算法自动做出了不连的选择。

代码实现

// 核心实现：动态规划递推，维护必要状态并避免重复处理。
class Solution {
    private int answer = -1001;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return answer;
    }

    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = Math.max(0, dfs(root.left));
        int right = Math.max(0, dfs(root.right));
        answer = Math.max(answer, root.val + left + right);
        return root.val + Math.max(left, right);
    }
}

// 核心实现：动态规划递推，维护必要状态并避免重复处理。
func maxPathSum(root *TreeNode) int {
    answer := -1001
    var dfs func(*TreeNode) int
    dfs = func(root *TreeNode) int {
        if root == nil {
            return 0
        }
        left := max(0, dfs(root.Left))
        right := max(0, dfs(root.Right))
        answer = max(answer, left+right+root.Val)
        return max(left, right) + root.Val
    }
    dfs(root)
    return answer
}

复杂度分析

时间复杂度：$O(n)$。凭什么：每个节点只被 dfs 访问一次，访问时做常数次比较与加法；所有 $O(n^2)$ 条候选路径都被"按最高点归类"压缩成了 n 次结算。

空间复杂度：$O(h)$，h 为树高，最坏（链状树）为 $O(n)$。凭什么：没有额外容器，只有递归调用栈和一个全局答案变量。

关键点总结

树形问题里"路径可以拐弯"的标准处理是给路径找唯一的最高点，把全局枚举转成对每个节点的一次局部结算，这个套路可以原样迁移到求直径、求最长同值路径等一大类题目。

递归返回单臂、结算双臂，是本题最容易混淆也最核心的一点；写代码前先把返回值的中文定义写在纸上，能规避绝大多数错误。

与 0 取大等价于"这一侧可以不要"，是负值场景下把可选性编码进数值的通用技巧，比用布尔标志分类讨论干净得多。

答案初值必须严格小于所有合法取值，凡是"路径至少含一个元素"且允许负数的题目都要检查这一点。

面试视角：这是困难题里出现频率极高的一道，面试官关心的往往不是代码而是你能否清楚区分"返回值"和"答案"两个量。回答时先说"我定义 dfs 返回从该节点向下的最大单链和"，再说"在每个节点用左右单链和加自身更新全局答案"，最后主动补充"与 53 题最大子数组和是同一种舍弃负前缀的思想"，基本就答满了。

易错点总结

错误写法：返回值写成 root.val + left + right → 树 [-10, 9, 20, null, null, 15, 7] 中根拿到 20 的返回值 42，再往上拼接就让 20 用到了三条边，返回 41 这种不存在的路径值。

错误写法：answer 初始化为 0 → 树 [-3] 的正确答案是 -3，实际返回 0，等价于允许了空路径。

错误写法：answer 初始化为 root.val 但后续忘记覆盖负分支 → 树 [2, -1] 时若结算式漏掉与 0 取大，会得到 1 而不是 2。

错误写法：漏掉 Math.max(0, ...)，直接用子树返回值 → 树 [1, -2, -3] 的正确答案是 1，实际结算成 1 + (-2) + (-3) = -4，被负分支拖垮。

错误写法：把与 0 取大写在结算之后、返回之前 → 结算时用的仍是未过滤的负值，树 [2, -1] 结算出 1，答案偏小。

错误写法：只在叶子处更新 answer → 树 [-10, 9, 20, null, null, 15, 7] 只会得到 20 这种单节点值，最优的 42 因为最高点不是叶子而被漏掉。

错误写法：空节点返回 Integer.MIN_VALUE 试图表示"不可用" → 与父节点的 root.val + left 相加立刻整型下溢变成大正数，答案变成天文数字。

错误写法：把返回值也参与更新答案，写成 answer = max(answer, dfs 的返回值) 而不结算双臂 → 树 [1, 2, 3] 的正确答案是 6，实际只得到 4，拐弯路径全部被忽略。

错误写法：Go 中把 answer 声明在 dfs 内部而不是闭包外部 → 每层递归各自持有一份变量，主函数读到的永远是初值 -1001。

错误写法：认为路径必须包含根或必须以叶子结尾 → 树 [-10, 9, 20, null, null, 15, 7] 会强行把根算进去得到 34，而正确答案 42 的路径根本不经过根。

相似题目

题目	难度	考察点
543. 二叉树的直径	简单	同为最高点拐弯模型，但结算的是边数而非权值和
687. 最长同值路径	中等	单臂延伸需附加"值相同"的条件，分支可用性要先判定
1245. 树的直径	中等	一般树的孩子个数不定，需在多个分支里取前两大
53. 最大子数组和	中等	一维退化版本，同样体现"负前缀直接舍弃"的思想
337. 打家劫舍 III	中等	返回值需携带选与不选两个分量，考察多状态返回
979. 在二叉树中分配硬币	中等	自底向上传递的是盈亏而非最值，答案累加边上流量