Hello 演算法活用指南：以「前序走訪 + 剪枝」範例三剖析回溯的三個核心動作

Hello 演算法活用指南：以「前序走訪 + 剪枝」範例三剖析回溯的三個核心動作

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

本篇以《Hello 演算法》zh-hant/codes/pythontutor/chapter_backtracking/preorder_traversal_iii_compact.md 這份 PythonTutor 視覺化程式為核心，逐步拆解一個極具代表性的回溯問題：在一棵二元樹中找出所有「根節點到值為 7 的節點」之路徑，且路徑上不得含有值為 3 的節點。讀完本文你將能掌握回溯演算法中「嘗試、回退、剪枝」三個核心動作的程式化寫法，理解何謂「狀態（path）」、「解（res）」與「約束條件」，並可一鍵執行、逐步視覺化驗證自己的理解。

1. 範例三問題：從「找節點」升級為「找受約束路徑」

在 backtracking_algorithm.md 一文的脈絡中，回溯的講解採用三個遞進的例題：

• 範例一：前序走訪整棵樹，收集所有值為 7 的節點；
• 範例二：進一步要求回傳「根節點到值為 7 節點」的整條路徑，因此在走訪時需要用path記錄路徑並在返回前撤銷；
• 範例三（本文主題）：在範例二之上追加約束條件，路徑中不可包含值為 3 的節點。

範例三的完整定義是：

在二元樹中搜尋所有值為 7 的節點，回傳根節點到這些節點的路徑，且要求路徑中不包含值為 3 的節點。

所謂「剪枝（pruning）」，正是針對這類「約束條件」發展出的技巧：當搜尋過程中遇到值為 3 的節點，就直接提前返回、不再深入其子樹，因為任何經過它的路徑都必然違反約束。從教材示意圖可以直觀看到，等於在搜尋樹上把「值為 3 的節點」所在的整個分支一併切除。

2. 視覺化檔案是什麼：一份可逐步執行的 PythonTutor 教學

這份preorder_traversal_iii_compact.md與一般章節講稿不同，它本體是一份PythonTutor 視覺化教學連結：Markdown 中以 URL-encoded 形式內嵌了完整的、可直接執行的 Python 程式，並以「[file]{preorder_traversal_iii_compact}-[func]{pre_order}」的標註方式，標明這段程式在整本教材的程式庫中對應的檔案與函式。原始程式位於 preorder_traversal_iii_compact.py（對應簡體版 codes/python 版本）。

在 PythonTutor 的執行畫面上，程式會依序高亮每一行程式碼並同步繪製「資料結構狀態」：path串列如何隨遞迴深入而增長、記錄解時res如何追加內容、遇到值為 3 的節點時如何被剪枝跳過、離開節點時path.pop()又如何讓路徑回退。這種「程式行 + 記憶體狀態」的同步呈現，正是學習遞迴與回溯最有效的輔助工具。

3. 完整程式剖析：前序走訪如何承載回溯三動作

以下是該視覺化頁面（亦即原始程式 preorder_traversal_iii_compact.py）的完整主體。它依賴 modules 中的TreeNode（二元樹節點）與list_to_tree（層序序列化建樹工具）：

def pre_order(root: TreeNode): """前序走訪：範例三""" # 剪枝 if root is None or root.val == 3: return # 嘗試 path.append(root) if root.val == 7: # 記錄解 res.append(list(path)) pre_order(root.left) pre_order(root.right) # 回退 path.pop()

這短短十餘行，已完整涵蓋回溯演算法的三個動作，與教材提煉的回溯術語表一一對應：

3.1 剪枝（pruning）：提前終止違反約束的分支

if root is None or root.val == 3: return

此處把兩種「不該繼續」的情況合併成一個出口：

• root is None：越過葉節點，無路可走；
• root.val == 3：命中約束條件，該節點及其整棵子樹都不可能產生合法路徑。

對應術語表中的「約束條件（constraint）：路徑中不包含節點 3」與「剪枝：當遇到值為 3 的節點時則不再繼續搜尋」。

3.2 嘗試（attempt）：做選擇並檢查是否為解

path.append(root) if root.val == 7: res.append(list(path))

先將目前節點加入路徑（此即「做出選擇、更新狀態」），再檢查是否抵達值為 7 的節點；若是，就把path的副本（list(path)）存入res。

這裡「複製而非直接存入引用」是關鍵細節：若不複製，res中所有條目都將指向同一個隨走訪而不斷變動的path物件，最終全部變成相同的空路徑。這也是 preorder_traversal_ii_compact 以來一脈相承的寫法。

3.3 回退（backtracking）：撤銷選擇、恢復原狀

pre_order(root.left) pre_order(root.right) path.pop()

遞迴探完左右子樹回到本節點後，path.pop()把當前節點移出路徑，讓path恢復到「進入本節點之前」的狀態，再返回上一層。這個「返回前必須撤銷自己造成的修改」的紀律，是回溯與普通 DFS 記錄程式最大的區別。

3.4 Driver Code 與預期輸出

if __name__ == "__main__": root = list_to_tree([1, 7, 3, 4, 5, 6, 7]) path = list[TreeNode]() res = list[list[TreeNode]]() pre_order(root) print("輸出所有根節點到節點 7 的路徑，路徑中不包含值為 3 的節點") for path in res: print([node.val for node in path])

以層序陣列[1, 7, 3, 4, 5, 6, 7]建立的樹，其結構為：根 1，左子 7（其左右子為 4、5），右子 3（其左右子為 6、7）。手動模擬走訪即可得到結論：

1. 根 1 → 左子7：path = [1, 7]，命中解，記錄[1, 7]；繼續深入 4、5 均非 7，返回後逐一彈出；
2. 根 1 → 右子3：立即觸發剪枝返回，值為 7 的那個葉節點永遠不會被走到。

因此程式輸出僅有一條路徑：

[1, 7]

想親眼驗證逐步過程，可開啟本文主題檔案 preorder_traversal_iii_compact.md，點入其中的 PythonTutor 連結逐行執行；或在終端直接執行 zh-hant/codes/python 版本 觀察列印結果。

4. 執行方式與多語言對照

教材強調「一鍵執行」，Python 版本的完整可執行程式位於：

• 繁體版：preorder_traversal_iii_compact.py
• 簡體版：codes/python 版本

Python 版本在匯入TreeNode、list_to_tree、print_tree時透過sys.path.append加入上一層路徑並from modules import ...，因此需在chapter_backtracking目錄環境下執行：

python3 preorder_traversal_iii_compact.py

其輸出會先以print_tree印出樹形結構，再印出[1, 7]。

同一函式在教材程式庫中提供了 12+ 種語言實現，例如 C、C++、Java、Go、JavaScript、Rust 等，均位於各語言的chapter_backtracking目錄下。以 C 語言為例，教材自行實現的TreeNode與listToTree位於 chapter_tree 工具標頭檔 等檔案中；JavaScript 則可依賴 modules 內的printTree呈現樹形。無論何種語言，pre_order的邏輯骨架（剪枝 → 嘗試 → 遞迴 → 回退）完全一致，非常適合跨語言比對學習。

5. 與回溯框架程式（template）的對照

教材在範例三之後，進一步將「嘗試、回退、剪枝」提煉成通用的回溯框架，並以範例三為案例給出框架版本實作，見 preorder_traversal_iii_template.py。框架將解題拆為六個可覆寫的環節：

對照可見，本文剖析的精簡版（compact）正是把is_valid/make_choice/undo_choice內聯進pre_order的結果。教材同時提醒：框架版本須刪除記錄解後的return，才能在找到值 7 的節點後繼續搜尋其他可能解（例如節點 7 的後代中若還有 7），精簡版中並無此return，二者的搜尋範圍差異可參考教材的對比示意圖。

兩種寫法的取捨亦很清晰：精簡版程式碼短、貼近前序走訪直覺；框架版較囉嗦，但通用性強，多數回溯問題（如 n 皇后、子集和、全排列）都可在該框架下透過定義state與choices快速套用。

6. 複雜度與學習重點總結

• 時間複雜度 O(n)：每個節點至多被造訪一次，剪枝只會減少而不會增加造訪數；
• 空間複雜度 O(n)：最壞情況（如鍊狀樹）下，遞迴棧深度與path長度均達樹高 n；
• 易錯點：記錄解時務必使用list(path)複製；path.pop()必須與path.append(root)成對出現；剪枝條件需放在「嘗試」之前，才能避免把違約節點寫進path。

透過「範例一 → 範例二 → 範例三」的遞進設計，教材把回溯最難理解的三件事——何時記錄解、為何要複製路徑、何謂剪枝——都濃縮在這一小段前序走訪中。建議讀者配合本主題 PythonTutor 檔案逐行執行程式，觀察path與res的即時變化，再回到 backtracking_algorithm.md 對照術語表與框架程式，即可奠定撰寫各類回溯題目的紮實基礎。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo