樹的回溯模板
範圍 — 樹的路徑問題背後那套「選擇 / 探索 / 復原」骨架，以及每題各自帶著的路徑狀態，外加根到葉卡片沒涵蓋的變形：通往單一節點的路徑（LC 236）、隱式的樹（LC 386、LC 388）；根到葉的卡片本身放在 tree_lca_distance.md。 另見：tree_lca_distance.md — 根到葉的路徑卡片（LC 112、113、129、257、437）；tree.md — 一般的樹走訪；binary_tree.md — DFS 狀態流動的方向；backtrack.md — 樹以外的回溯。
很多樹的路徑問題共用同一套 DFS 骨架：選擇（延伸路徑狀態）、檢查目標（通常在葉子）、探索兩個子節點、復原。這份表單講的是骨架，以及每題帶著什麼狀態；標準的根到葉卡片（LC 112、113、129、257、437）放在 tree_lca_distance.md，下面各節會連過去。
LeetCode 題目清單
1️⃣ 通用樹回溯模板
void dfs(TreeNode node, ...) {
if (node == null) return;
// 1. choose (update path / sum / state)
// 2. check goal (usually leaf condition)
// 3. explore children
dfs(node.left, ...);
dfs(node.right, ...);
// 4. undo choice (backtrack)
}
處理路徑問題時，通常要維護：
List<Integer> path
some running state (sum / number / string)
2️⃣ 完整的通用模板
void dfs(TreeNode node, List<Integer> path, int state) {
if (node == null) return;
// choose
path.add(node.val);
state = update(state, node.val);
// goal check
if (isLeaf(node) && condition(state)) {
save(path);
}
// explore
dfs(node.left, path, state);
dfs(node.right, path, state);
// undo (backtrack)
path.remove(path.size() - 1);
}
關鍵步驟：
| 步驟 | 用途 |
|---|---|
| choose | 把節點加進路徑 |
| check | 看看是否達成目標 |
| explore | 對子節點做 DFS |
| undo | 還原狀態 |
3️⃣ 套用到 LC 113（Path Sum II）
狀態 = 剩下的總和，再加上一個進入時 append、離開時 pop 的路徑 list。完整的卡片（Python 與 Java、試跑和陷阱）在 tree_lca_distance § Template 4，那份表單負責整個根到葉路徑家族。
4️⃣ 套用到 LC 257（Binary Tree Paths）
狀態 = 路徑字串。字串不可變，每次呼叫各自建出自己的一份，沒有東西要復原。完整解法在 tree_lca_distance § Template 4 的 Path Update Strategies，旁邊就是拿來對照的可變 list 版本。
5️⃣ 套用到 LC 129（根 → 葉的數字）
狀態 = 數字：num * 10 + node.val，以值傳遞，所以同樣沒有東西要復原。完整解法是 Sum Root to Leaf Numbers — LC 129。
6️⃣ 特殊情況：LC 437（Path Sum III）
LC 437 的路徑往下走時可以從任何地方開始，不一定是根。從每個節點各跑一次模板行得通，但在歪斜的樹上是 O(N²)。O(N) 的版本回溯的是一張前綴和 map 而不是 list — 見下面的 §1️⃣1️⃣。
7️⃣ 心智模型（非常重要）
只要看到：
root → leaf
path
all paths
sum of paths
string of paths
馬上就該想到：
DFS + Backtracking
模板：
add node
check leaf
dfs children
remove node
8️⃣ 面試速記密技 優先度 1／5 — 加分項
把這個五行骨架背起來就好：
path.add(node.val);
if (leaf condition)
save result;
dfs(left)
dfs(right)
path.remove(path.size()-1);
大多數根到葉的題目用這個就能解掉。
✅ 面試小訣竅
如果題目裡出現這些字眼：
all paths
root to leaf
return list of paths
那幾乎保證是 DFS＋回溯。
9️⃣ 快速決策表（該用哪個路徑模板？）
| 路徑上要做的事 | 模板 | 復原步驟 | 例題 |
|---|---|---|---|
| 收集所有根到葉的路徑 | push 節點／pop 節點 | path.remove(size-1) |
LC 113、LC 257 |
| 把路徑摺疊成一個純量（和／數字） | 用傳值的方式帶狀態 | 不用復原 — 值是複製的 | LC 129 |
| 找到通往某一個節點的路徑 | push，只在失敗時 pop | 子樹回傳 false 時才 pop | LC 236 |
| 統計和為目標值的子路徑數 | 路徑上的前綴和計數器 | count[cur] -= 1 |
LC 437 |
| 走訪隱含的樹（數字／文字） | 從父節點狀態重建子節點 | 除回去／彈堆疊 | LC 386、LC 388 |
⭐⭐⭐⭐⭐ 這幾種之間唯一的差別，就是**「路徑狀態」是什麼**，以及要怎麼把它復原。
🔟 模板：根→節點的路徑，只在失敗時復原（LC 236）
核心想法：標準模板在探索完子節點後會無條件 pop。
但當你在找某一個特定節點時，改成只有子樹失敗才 pop——
這樣搜尋成功時，path 裡剛好留著完整的根→目標路徑。
模式：分別建出 path(root→p) 和 path(root→q)，兩者最後一個共同前綴元素就是 LCA。
// java
// LC 236 - Lowest Common Ancestor of a Binary Tree
// IDEA: collect root->p and root->q paths with backtracking (pop on failure only),
// then walk both paths together; last shared node = LCA.
class Solution {
// time = O(N), space = O(H) (H = tree height, O(N) worst case)
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
List<TreeNode> pathP = new ArrayList<>(), pathQ = new ArrayList<>();
findPath(root, p, pathP);
findPath(root, q, pathQ);
TreeNode lca = null;
for (int i = 0; i < Math.min(pathP.size(), pathQ.size()); i++) {
if (pathP.get(i) != pathQ.get(i)) break; // prefix ended
lca = pathP.get(i);
}
return lca;
}
private boolean findPath(TreeNode node, TreeNode target, List<TreeNode> path) {
if (node == null) return false;
path.add(node); // choose
if (node == target) return true; // goal -> KEEP the path
if (findPath(node.left, target, path)) return true;
if (findPath(node.right, target, path)) return true;
path.remove(path.size() - 1); // undo ONLY on failure
return false;
}
}
# python
# LC 236 - Lowest Common Ancestor of a Binary Tree
# IDEA: same backtracking, pop only when the subtree does not contain the target
class Solution(object):
# time = O(N), space = O(H)
def lowestCommonAncestor(self, root, p, q):
def find_path(node, target, path):
if not node:
return False
path.append(node) # choose
if node is target:
return True # goal -> keep path
if find_path(node.left, target, path) or find_path(node.right, target, path):
return True
path.pop() # undo ONLY on failure
return False
path_p, path_q = [], []
find_path(root, p, path_p)
find_path(root, q, path_q)
lca = None
for a, b in zip(path_p, path_q):
if a is not b:
break
lca = a
return lca
為什麼要學這個，而不是那個有名的三行後序 LCA？ 面試官追問時，活下來的是路徑版：「回傳 p 和 q 之間的距離」、 「印出 p 到 q 的路徑」、「不保證兩個節點都存在」（看那個布林回傳值）。 三行版在只有 p 或 q 其中一個存在時，還是會默默回傳一個節點。
1️⃣1️⃣ 模板：在路徑上做前綴和＋復原（LC 437）
§6️⃣ 的「從每個節點做 DFS」是 O(N²)。O(N) 的做法把目前根到節點的路徑當成陣列，套用子陣列和的技巧：一張記錄目前路徑上前綴和的 map，回程時復原 — 在這裡 map 就是路徑狀態，就像 LC 113 的 list 一樣。完整的卡片（Python、Java、試跑，以及陷阱：prefix[0] = 1、復原、Java 的 long）在 tree_lca_distance § Template 5。
1️⃣2️⃣ 模板：在隱含的樹上回溯（LC 386）
不是每棵樹都由 TreeNode 組成。1..n 依字典序排列，本身就是一棵 10 元的 trie：
1 → 10 → 100 …，而字典序恰好就是它的前序走訪。
模式：子節點 = parent * 10 + d。child > n 時剪枝。
// java
// LC 386 - Lexicographical Numbers
// IDEA: preorder DFS over the implicit 10-ary trie of numbers; child = cur*10 + d
class Solution {
// time = O(N), space = O(log N) recursion depth
public List<Integer> lexicalOrder(int n) {
List<Integer> res = new ArrayList<>();
for (int i = 1; i <= 9; i++) dfs(i, n, res); // 9 trie roots
return res;
}
private void dfs(int cur, int n, List<Integer> res) {
if (cur > n) return;
res.add(cur); // preorder: visit before children
for (int d = 0; d <= 9; d++) {
int next = cur * 10 + d;
if (next > n) break; // prune (d only grows)
dfs(next, n, res);
}
}
}
# python
# LC 386 - Lexicographical Numbers
# IDEA: preorder DFS on the implicit 10-ary trie of 1..n
class Solution(object):
# time = O(N), space = O(log N)
def lexicalOrder(self, n):
res = []
def dfs(cur):
if cur > n:
return
res.append(cur)
for d in range(10):
nxt = cur * 10 + d
if nxt > n:
break
dfs(nxt)
for i in range(1, 10):
dfs(i)
return res
追問（O(1) 額外空間） — 面試官最愛的變化。同樣的走法，改成迭代；
「往上回到父節點」變成除以 10：
// java
// LC 386 - Lexicographical Numbers (O(1) space, explicit backtracking)
// IDEA: go down (*10) when possible, else move right (+1),
// else climb (/10) until a right sibling exists.
class Solution {
// time = O(N), space = O(1) excluding output
public List<Integer> lexicalOrder(int n) {
List<Integer> res = new ArrayList<>();
int cur = 1;
for (int i = 0; i < n; i++) {
res.add(cur);
if ((long) cur * 10 <= n) {
cur *= 10; // go deeper
} else {
while (cur % 10 == 9 || cur + 1 > n) cur /= 10; // backtrack up
cur++; // next sibling
}
}
return res;
}
}
# python
# LC 386 - Lexicographical Numbers (O(1) space, explicit backtracking)
class Solution(object):
# time = O(N), space = O(1) excluding output
def lexicalOrder(self, n):
res, cur = [], 1
for _ in range(n):
res.append(cur)
if cur * 10 <= n:
cur *= 10 # go deeper
else:
while cur % 10 == 9 or cur + 1 > n:
cur //= 10 # backtrack up
cur += 1 # next sibling
return res
1️⃣3️⃣ 模板：用深度當鍵的路徑狀態堆疊（LC 388）
一段有縮排的文字就是一棵序列化的樹，tab 的數量就是深度。 你完全不用把樹建出來——只要保留當前根→節點的路徑長度， 一旦跳到比較淺的深度，較深的那些項目就自動被丟掉（也就是回溯）。
核心想法：pathLen[d] = 深度 d 處的目錄前綴長度。
由上往下掃描時寫入 pathLen[depth + 1]，會覆蓋掉任何殘留的兄弟分支，
這正好就是經典模板裡的「pop」。
// java
// LC 388 - Longest Absolute File Path
// IDEA: implicit tree from indentation; pathLen[depth] = prefix length of current root->node path.
// A shallower line overwrites the deeper entries => automatic backtrack.
class Solution {
// time = O(N) over input chars, space = O(D) depth
public int lengthLongestPath(String input) {
Map<Integer, Integer> pathLen = new HashMap<>();
pathLen.put(0, 0); // depth 0 has no prefix
int best = 0;
for (String line : input.split("\n")) {
int depth = line.lastIndexOf('\t') + 1; // tabs are always leading
String name = line.substring(depth);
if (name.contains(".")) { // leaf = file
best = Math.max(best, pathLen.get(depth) + name.length());
} else { // internal node = dir
pathLen.put(depth + 1, pathLen.get(depth) + name.length() + 1); // +1 for '/'
}
}
return best;
}
}
# python
# LC 388 - Longest Absolute File Path
# IDEA: depth-keyed path-length map; deeper stale entries are overwritten, never reused
class Solution(object):
# time = O(N), space = O(D)
def lengthLongestPath(self, input):
best = 0
path_len = {0: 0}
for line in input.split('\n'):
name = line.lstrip('\t')
depth = len(line) - len(name)
if '.' in name: # file -> leaf
best = max(best, path_len[depth] + len(name))
else: # dir -> internal node
path_len[depth + 1] = path_len[depth] + len(name) + 1 # +1 for '/'
return best
容易踩到的坑
- 完全沒有檔案時要回傳
0（"a"→0），而不是最長的目錄路徑。 - 那個
+1是/分隔符；深度0的檔案剛好不會多一個分隔符。 - 用
Deque<Integer>一路彈到size == depth，是同一件事的顯式堆疊寫法。
1️⃣4️⃣ 變形：狀態往下流，結構往上改（LC 1110）
骨架相同，但不是往路徑上 push，而是把一個布林值往下傳（「我的父節點被刪了，所以我是一棵新樹的根」），並把重接好的子樹往上回傳（被刪的節點回傳 None，父節點就把那條連結拿掉）。這是改樹的結構而不是路徑問題，所以它的卡片和其他結構修改放在一起：binary_tree § Template 10。
1️⃣5️⃣ 路徑模板總表
| LC | 題目 | 路徑狀態 | 復原方式 |
|---|---|---|---|
| 113 | Path Sum II | List<Integer> ＋剩餘的和 |
path.remove(size-1) |
| 257 | Binary Tree Paths | 字串（傳值） | 隱含 |
| 129 | Sum Root to Leaf Numbers | int num（傳值） |
隱含 |
| 236 | Lowest Common Ancestor | 節點 list，失敗才 pop | 有條件的 pop |
| 437 | Path Sum III | Map<prefixSum, count> |
count[cur] -= 1 |
| 386 | Lexicographical Numbers | 目前的數字 | cur /= 10 |
| 388 | Longest Absolute File Path | pathLen[depth] |
覆寫／彈到該深度 |
| 1110 | Delete Nodes And Return Forest | parentWasDeleted 旗標 |
往上回傳 null |