# DoorDash VO 面试题：二叉树两“存活”节点间最大路径和（树形 DP / 后序 DFS）
本文由 oavoservice 以面试复盘风格整理：给出题意澄清、可落地的状态定义、边界处理与可写出来的代码模板。
题目（改写版）
给定一棵二叉树，每个节点有整数权重。
- Part A：把“存活节点（alive）”定义为 叶子节点。求任意两端点都为 alive 的路径中，路径和的最大值。
- Part B（Follow-up）：一些内部节点也可能是 alive。要求路径两端点是 alive，且路径中间不能再出现其他 alive 节点。求最大路径和。
路径必须沿父子指针连续。
面试澄清点
- 路径必须是树上简单路径（不会重复节点）。
- 是否允许只选一个节点？通常要求“两端点都是 alive”，所以至少要能选出两端点。
- 节点权重可能为负。
Part A：alive = 叶子节点
这是经典“最大路径和”变体，但端点必须是叶子。
思路
后序 DFS，返回：
down[u]：从u往下到 某个叶子 的最大路径和（必须落到叶子）。
在 u 处，如果左右子树都存在（都能提供叶子），则可以用 down[left] + val[u] + down[right] 更新全局答案（叶子到叶子）。
复杂度
- 时间：
O(n) - 空间：
O(h)递归栈（h 为树高）
Python 代码模板
from math import inf
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def max_leaf_to_leaf_sum(root: TreeNode) -> int:
ans = -inf
def dfs(node: TreeNode) -> int:
nonlocal ans
if not node:
return -inf
# 叶子：down 就是自己
if not node.left and not node.right:
return node.val
left_down = dfs(node.left) if node.left else -inf
right_down = dfs(node.right) if node.right else -inf
# 如果两侧都存在叶子路径，则可形成叶子-叶子
if node.left and node.right:
ans = max(ans, left_down + node.val + right_down)
# down 必须走向存在的那一侧
return node.val + max(left_down, right_down)
down_root = dfs(root)
# 若整棵树无法形成叶子-叶子（比如链状树），通常面试可约定返回 down_root 或者报错。
# 这里选择：若 ans 没被更新，则返回 down_root（从根到某叶子的最大和）。
return ans if ans != -inf else down_root
Part B：内部节点也可能 alive（路径中间禁止出现 alive）
这题的关键是：路径必须在两端遇到 alive，中间不能经过 alive。
状态设计（可扩展）
后序 DFS，给每个节点返回两类信息：
best_end[u]：从u往下走、在子树内找到一个 alive 作为端点的“最佳向下路径和”，但要求这条向下路径上（不含端点 alive）不再包含 alive。is_alive[u]：当前节点是否 alive。
转移时：
- 如果
u自己是 alive，那么best_end[u] = val[u]，并且不允许继续向下穿过（因为中间不能出现 alive）。 - 如果
u不是 alive，那么它可以连接左/右子树的best_end。 - 形成答案的方式：在某个节点
u处，将来自左右子树的两个 alive 端点路径通过u拼起来：left_best + val[u] + right_best。
代码模板（alive 集合作为输入）
from math import inf
def max_alive_to_alive_sum(root: TreeNode, alive: set[TreeNode]) -> int:
ans = -inf
def dfs(node: TreeNode) -> int:
nonlocal ans
if not node:
return -inf
node_is_alive = node in alive
left_best = dfs(node.left)
right_best = dfs(node.right)
# 如果当前节点是 alive：它只能作为端点，不能作为“中间”继续向下连接
if node_is_alive:
ans = max(ans, node.val) # 允许两端点同一个点？按需调整
return node.val
# 当前节点不是 alive：可以把子树里的 alive 端点“往上带”
best_end = node.val + max(left_best, right_best)
# 如果左右两边都各自能提供 alive 端点，则在这里拼成 alive->alive
if left_best != -inf and right_best != -inf:
ans = max(ans, left_best + node.val + right_best)
return best_end
dfs(root)
return ans
面试官常追问
- 为什么
-inf比None更好用（方便 max/比较）？ - 链状树不能形成叶子-叶子时返回什么？需要提前对齐面试约定。
- 节点值为负时，为什么不能随便丢弃子路径（端点约束会强制选路径）。
如果你在准备 DoorDash / Snowflake / Google 等公司的 VO，我们在 oavoservice 会把这类“经典题的变体约束”训练到能在 5 分钟内说清状态定义与边界。
需要面试真题？ 立刻联系微信 Coding0201，获得真题。