🔬 Saturday Deep Dive: Binary Tree Maximum Path Sum (15 min read)
📊 NeetCode: 58/150 · SysDesign: 57/40 · Behavioral: 57/40 · Frontend: 37/50 · AI: 28/30
🔥 Day 71 — Expert Phase
Overview / 概述
中文： 二叉树最大路径和是 LeetCode 上最经典的困难题之一，也是面试高频题。它难在哪里？不是数据结构复杂，而是需要在同一个 DFS 递归里同时维护两种不同语义的值：
- 向上返回给父节点的值（只能选一条分支）
- 本地最优解（可以跨越当前节点，同时利用左右两条分支）
这种"局部观察 vs 全局维护"的模式在很多树问题里都会出现，掌握它能让你在面试中举一反三。
English: Binary Tree Maximum Path Sum is one of LeetCode's most iconic Hard problems. The difficulty isn't the data structure — it's managing two semantically different values inside a single DFS pass:
- What to return to the parent (only one branch allowed — otherwise you'd create a cycle)
- The local best candidate (the path can arch through the current node using both left + right branches)
This "local candidate vs. global tracker" pattern appears repeatedly in tree problems. Mastering it unlocks a whole class of similar challenges.
🔗 LeetCode: https://leetcode.com/problems/binary-tree-maximum-path-sum/
📹 NeetCode: https://www.youtube.com/watch?v=Hr5cWUld4vU
Part 1: Theory / 理论基础 (5 min)
什么是路径？/ What is a "path"?
中文： 在这道题里，"路径"的定义很重要：
- 路径是树中任意一组节点的序列，序列中每对相邻节点之间有边相连
- 路径不需要经过根节点
- 每个节点最多出现一次
- 路径可以只包含单个节点
关键约束：路径是一条连续的线，不能分叉。一旦你选择了左子树的路径，就不能再往右子树延伸后"折回"。
English: The definition of "path" here is crucial:
- A path is any sequence of nodes where each adjacent pair is connected by an edge
- The path does not need to pass through the root
- Each node appears at most once
- A path can consist of just a single node
Key constraint: a path is a continuous line — no forking. Once you go left, you can't also go right and come back.
两种视角 / Two Perspectives
中文： 解题的核心洞察是：对同一个节点，我们需要用两种视角来看：
视角 1 — 作为子树根节点（局部最优）：
这个拱形路径的和 = left_gain + node.val + right_gain。
但这条路径无法再向上延伸（因为它已经分叉了），所以它只用于更新全局最大值。
视角 2 — 作为父节点的一段延伸（向上贡献）：
当前节点能贡献给父节点的最大值 = node.val + max(left_gain, right_gain, 0)。
只能选左或右一条分支（不能同时选），且如果两条分支都是负的，贡献为 0（不如不选）。
English: The core insight is that every node plays two roles simultaneously:
Role 1 — Local arch candidate:
The current node can "arch" through both children: left_gain + node.val + right_gain.
This arch can't extend further upward (it forks), so it's only used to update the global max.
Role 2 — Upward contributor:
The max gain the current node can contribute to its parent = node.val + max(left_gain, right_gain, 0).
Must pick only one branch (left or right), and if both are negative, contribute 0 (better not to extend).
为什么需要全局变量？/ Why a global variable?
中文： 因为最优路径可能不经过树的根节点。如果只看递归的返回值，我们可能会错过那些"拱形"路径（选了左右两条分支后就无法再向上返回了）。全局变量 max_sum 在每个节点都被更新一次，保证我们捕获了所有可能的路径。
English: Because the optimal path might exist deep in the subtree without ever touching the root. If we only look at return values, we'd miss "arch" paths (which consume both branches and can't propagate further up). The global max_sum is updated at every node, ensuring we capture every candidate path.
Part 2: Step-by-Step Implementation / 一步一步实现 (8 min)
朴素思路 → 最优解 / Naive → Optimal
朴素思路（会超时）：
对每个节点，把它当做路径的"最高点"，然后 DFS 搜索所有经过它的路径。
时间复杂度 O(n²)，不够用。
最优思路（O(n)）：
一次 DFS 遍历，在每个节点同时做两件事：
- 更新全局最大值（考虑拱形路径）
- 返回向上的最大贡献
完整实现 / Complete Implementation
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
# Global tracker: initialized to -infinity because all nodes
# could be negative (e.g., a tree with only -3 → answer is -3)
self.max_sum = float('-inf')
def dfs(node: Optional[TreeNode]) -> int:
"""
Returns: the maximum gain this subtree can contribute
to its PARENT (single-branch, no arching allowed).
Side effect: updates self.max_sum with the best arch path
rooted at `node`.
"""
if not node:
# Null nodes contribute 0 (base case)
return 0
# --- Step 1: Recurse on children ---
# Use max(..., 0) to "ignore" negative branches.
# If going left makes things worse, we just don't go left.
left_gain = max(dfs(node.left), 0)
right_gain = max(dfs(node.right), 0)
# --- Step 2: Compute local arch path (Role 1) ---
# This path passes THROUGH the current node using both branches.
# It is a valid path from the deepest left leaf to deepest right leaf.
# It CANNOT be extended upward (already forked), so only update global max.
arch_path_sum = node.val + left_gain + right_gain
self.max_sum = max(self.max_sum, arch_path_sum)
# --- Step 3: Return upward contribution (Role 2) ---
# Parent can only extend one direction.
# Pick the branch that gives more gain.
return node.val + max(left_gain, right_gain)
dfs(root)
return self.max_sum逐步追踪一个例子 / Tracing Through an Example
Tree:
-10
/ \
9 20
/ \
15 7DFS 调用顺序（后序遍历）：
关键细节解析 / Key Detail Analysis
为什么用 max(dfs(...), 0) 而不是直接用返回值？
# BAD: forces us to include negative subtrees
left_gain = dfs(node.left)
# GOOD: "prune" negative contributions — don't extend if it hurts
left_gain = max(dfs(node.left), 0)中文： 如果左子树最好的路径是 -5，我们不应该把它加进来。max(..., 0) 相当于"如果这条路是负的，就当成没有这条路"。这避免了显式的 None 检查和负值处理。
English: If the best path in the left subtree sums to -5, we're better off not extending there. max(..., 0) is a clean idiom for "treat negative subtrees as nonexistent." This eliminates explicit null checks and negative-branch edge case handling.
变体 1：追踪路径（不只是数值）/ Variant: Track the Actual Path
class Solution:
def maxPathSumWithPath(self, root: Optional[TreeNode]):
self.max_sum = float('-inf')
self.best_path = []
def dfs(node):
if not node:
return 0, []
left_gain, left_path = dfs(node.left)
right_gain, right_path = dfs(node.right)
left_gain = max(left_gain, 0)
right_gain = max(right_gain, 0)
# Build the arch path for comparison
arch = node.val + left_gain + right_gain
if arch > self.max_sum:
self.max_sum = arch
# Reconstruct path: left reversed + current + right
arch_path = (
(left_path if left_gain > 0 else []) +
[node.val] +
(right_path if right_gain > 0 else [])
)
self.best_path = arch_path
# Return single-branch path upward
if left_gain >= right_gain:
return node.val + left_gain, [node.val] + left_path
else:
return node.val + right_gain, [node.val] + right_path
dfs(root)
return self.max_sum, self.best_path变体 2：迭代写法（Morris / 显式栈）/ Iterative Variant
def maxPathSumIterative(self, root: Optional[TreeNode]) -> int:
"""
Post-order traversal using an explicit stack.
Useful when recursion depth is a concern (very deep trees → stack overflow).
"""
if not root:
return 0
max_sum = float('-inf')
# Stack stores (node, visited_flag)
stack = [(root, False)]
# Stores the best upward gain for each node
gain = {}
while stack:
node, visited = stack.pop()
if visited:
# Post-order: both children are processed
left_gain = max(gain.get(node.left, 0), 0)
right_gain = max(gain.get(node.right, 0), 0)
arch = node.val + left_gain + right_gain
max_sum = max(max_sum, arch)
# Store upward contribution for parent
gain[node] = node.val + max(left_gain, right_gain)
else:
# Push self back as "visited", then children
stack.append((node, True))
if node.right:
stack.append((node.right, False))
if node.left:
stack.append((node.left, False))
return max_sum复杂度分析 / Complexity
| 时间 Time | 空间 Space | |
|---|---|---|
| 递归 Recursive | O(n) | O(h) — 调用栈深度 call stack depth |
| 迭代 Iterative | O(n) | O(n) — 显式栈 + gain 字典 |
其中 h = 树高，最坏情况（链状树）h = n，平衡树 h = log n。
Part 3: Edge Cases & Gotchas / 边界情况 (2 min)
1. 全负数树 / All Negative Values
root = TreeNode(-3)
# Expected: -3 (the single node is the path)
# Bug: initializing max_sum = 0 would wrongly return 0
# Fix: initialize to float('-inf'), NOT 02. 单节点树 / Single Node
root = TreeNode(5)
# dfs returns 5, arch_path_sum = 5, max_sum = 5 ✓3. 路径不过根节点 / Optimal Path Doesn't Touch Root
# -100
# / \
# 1 2
# / \
# 50 50
# Best path: 50 + 1 + 50 = 101, ignores -100 at root由于 max_sum 在每个节点都更新，我们不会遗漏这种情况。
4. 忘记 max(..., 0) / Forgetting to Clamp Negative Gains
# Without clamping:
left_gain = dfs(node.left) # could be -999
arch = node.val + (-999) + right_gain # incorrectly penalized
# With clamping:
left_gain = max(dfs(node.left), 0) # negative branch = 05. 负数根但有正路径 / Negative Root with Positive Deep Path
# -1
# / \
# 10 10
# Best path: 10 + (-1) + 10 = 19 — still valid, arch through root
# OR simply: 10 alone if root was even more negativePart 4: Real-World Application / 实际应用 (2 min)
中文： 这道题的模式在生产系统中出处不少：
1. 金融 / Finance — 最优投资路径：
树结构表示一个投资决策树（每个节点是一项投资，边代表序列依赖关系）。最大路径和 = 最优投资组合的总收益。
2. 网络路由 / Network Routing — 最大带宽路径：
在树形网络拓扑中（如 ISP 骨干网），找两个叶节点之间带宽最大的路径，同样是树中最大路径和的变体。
3. 游戏 AI / Game AI — 行动序列价值：
棋类游戏里，博弈树的某个子树中最有价值的"连续行动序列"，本质上就是子树中的最大路径。
4. 编译器 / Compilers — 表达式树优化：
在 AST（抽象语法树）中，找出对性能影响最大的表达式链，指导内联或循环展开决策。
English: This pattern appears in real production systems:
- Finance: Portfolio optimization over decision trees — find the sequence of investments with maximum total return
- Network routing: In tree-topology networks (ISP backbone), find the max-bandwidth path between any two leaf nodes
- Game AI: In game trees, the most valuable sequence of moves in a subtree is a maximum path problem
- Compilers: In ASTs, identifying the expression chain with the highest performance impact guides inlining decisions
Part 5: Interview Simulation / 面试模拟 (3 min)
Q1: 为什么 DFS 返回值不能是"拱形路径"的和？
Why can't the DFS return value be the arch path sum?
A: 因为返回值会被父节点用来向上延伸路径。拱形路径已经使用了两个方向（左 + 右），如果父节点再把它向上接，就相当于节点被访问两次——这破坏了"路径"中每个节点只出现一次的约束。所以拱形结果只能更新全局 max，不能向上传递。
Because the return value is used by the parent to extend the path upward. An arch path has already forked left and right — if the parent tries to continue from it, a node would appear twice in the path (violating the problem's uniqueness constraint). So arch values only update the global max; they never propagate upward.
Q2: 如果树可能有几百万节点，递归会栈溢出怎么办？
What if the tree has millions of nodes and recursion hits stack limits?
A: 用显式栈做后序遍历（见变体 2），把递归调用栈换成堆上的数据结构。Python 默认递归限制约 1000 层，对链状树（最坏情况）可以用 sys.setrecursionlimit() 或直接用迭代版本。
Use an explicit stack for iterative post-order traversal (see Variant 2 above). Python's default recursion limit is ~1000 frames — for degenerate (linear chain) trees, either increase sys.setrecursionlimit() or switch to the iterative version.
Q3: 这道题的哪部分最容易出 bug？
What's the most common bug in this problem?
A: 两个地方：(1) 将 max_sum 初始化为 0 而不是 -inf，导致全负数树返回错误的 0；(2) 忘记用 max(..., 0) 截断负增益，导致强行走负路径拉低结果。
Two places: (1) initializing max_sum = 0 instead of float('-inf'), which breaks all-negative trees; (2) forgetting max(..., 0) to clamp negative gains, forcing the algorithm to extend into costly negative subtrees.
Q4: 如何将这道题推广到 N 叉树（每个节点有多个子节点）？
How would you generalize this to an N-ary tree?
A: 思路完全相同，只是"局部最优（拱形）"变成：取所有子节点中增益 > 0 的子节点，全部加进来。向上贡献则取所有子节点中最大的那一个。代码里把 left_gain + right_gain 改为对所有子节点的正增益求和即可。
Same idea — the "arch" at any node is: take the sum of all child gains that are positive (include any direction that helps). The upward contribution is still just the single best child. Replace left_gain + right_gain with sum(max(dfs(child), 0) for child in node.children).
Q5: 如果路径要求至少包含 K 个节点，怎么改？
How would you modify this if the path must contain at least K nodes?
A: 这变成了一道更复杂的题。需要在 DFS 状态里额外追踪"路径长度"，并且只有当路径长度 ≥ K 时才更新全局最大值。同时，max(..., 0) 的剪枝也需要更谨慎——即使某段是负的，如果路径还不够长，也可能不得不选它。通常会变成 DFS + 状态压缩或 DP on tree 的问题。
This becomes significantly harder. You'd need to track "path length" in the DFS state and only update the global max when the path has ≥ K nodes. The max(..., 0) pruning also becomes unsafe — you might be forced to extend into a negative-gain subtree just to satisfy the length requirement. This typically becomes a DP-on-tree problem.