知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 12 - 二叉树中的最大路径和 ## 题目(LeetCode 124) 给定一棵二叉树,找出路径和最大的路径。路径可以从任意节点出发,到任意节点结束(不需要经过根节点),但路径方向必须是连续的(不能走回头路)。 ``` -10 / \ 9 20 / \ 15 7 最大路径和 = 42(路径:15 → 20 → 7) ``` ## 大白话理解 这道题是"二叉树的直径"的升级版。直径求的是最长路径的边数,这道题求的是最大路径的节点值之和,而且节点值可以是负数。 核心思想和直径一模一样:对于每个节点,经过它的路径有两种形态: ``` 形态 1:拐弯路径(经过当前节点,连接左右子树) 当前节点 / \ 左链 右链 路径和 = 左链最大贡献 + 当前节点值 + 右链最大贡献 形态 2:单链路径(不拐弯,只走一边,给父节点用) 父节点 | 当前节点 / 或 \ 左链 右链 贡献值 = 当前节点值 + max(左链最大贡献, 右链最大贡献) ``` 关键区分: - "拐弯路径"是用来更新全局最大值的(这条路径到当前节点就结束了,不能再往上延伸) - "单链贡献"是返回给父节点的(父节点还要继续往上连) ## 代码 ```java class Solution { private int maxSum = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { maxGain(root); return maxSum; } // 返回:以 node 为端点的单链最大贡献值 private int maxGain(TreeNode node) { if (node == null) return 0; // 左右子树的最大贡献(如果是负数就不要,取 0) int leftGain = Math.max(maxGain(node.left), 0); int rightGain = Math.max(maxGain(node.right), 0); // 经过当前节点的"拐弯路径"的和 int pathSum = node.val + leftGain + rightGain; // 更新全局最大值 maxSum = Math.max(maxSum, pathSum); // 返回给父节点的贡献(只能选一边,不能拐弯) return node.val + Math.max(leftGain, rightGain); } } ``` ## 逐行拆解 ``` maxGain(node) 的含义: 从 node 出发,往下走(只走一边),能获得的最大路径和 这个值是给父节点用的 为什么 Math.max(..., 0)? 如果子树的贡献是负数,还不如不走(贡献为 0) 比如左子树贡献 -5,那就不走左边了 pathSum = node.val + leftGain + rightGain 这是经过当前节点的"拐弯路径"的总和 左边最好的 + 自己 + 右边最好的 用这个值更新全局最大值 return node.val + Math.max(leftGain, rightGain) 返回给父节点时只能选一边(选贡献大的那边) 因为路径不能分叉,从父节点的角度看,只能从一边过来 ``` ## 画图模拟 ``` -10 / \ 9 20 / \ 15 7 从下往上计算: 节点 9: 左0 右0 → pathSum = 9+0+0 = 9 → maxSum=9 返回 9+max(0,0) = 9 节点 15: 左0 右0 → pathSum = 15+0+0 = 15 → maxSum=15 返回 15 节点 7: 左0 右0 → pathSum = 7+0+0 = 7 → maxSum=15 返回 7 节点 20: 左15 右7 → pathSum = 20+15+7 = 42 → maxSum=42 ✓ 返回 20+max(15,7) = 35 节点 -10: 左9 右35 → pathSum = -10+9+35 = 34 → maxSum=42(不更新) 返回 -10+max(9,35) = 25 最终答案:42(路径 15 → 20 → 7) ``` ## 和"直径"题的对比 ``` 直径(LeetCode 543): depth(node) 返回深度 直径 = max(leftDepth + rightDepth) 每个节点都算"左深度 + 右深度",取最大 最大路径和(LeetCode 124): maxGain(node) 返回最大贡献值 最大路径和 = max(node.val + leftGain + rightGain) 每个节点都算"拐弯路径和",取最大 额外处理:负数贡献取 0(不走比走好) 本质上是同一个套路: 后序遍历,返回值给父节点用,顺便更新全局最大值 ``` ## 为什么是 Hard? 难点不在代码量(代码很短),而在于想清楚两件事: 1. 返回给父节点的值(单链)和更新全局最大值的值(拐弯)是不同的 2. 负数贡献要舍弃(取 0) 想明白这两点,代码就水到渠成了。 ## 复杂度 - 时间:O(n),每个节点访问一次 - 空间:O(h),递归栈深度 ## 一句话总结 后序遍历,每个节点算"拐弯路径和"更新全局最大值,返回"单链贡献"给父节点。负数贡献直接丢弃。 --- 上一篇:[11 - 路径总和 III](./11-path-sum-iii.md) | 返回:[目录](./README.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入