本文由 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，獲得真題。