樹的基本結構是數據結構中非常重要的概念，它由節點和邊組成，其中每個節點可以有多個子節點（子樹），但只有一個父節點（根節點除外）。比如，一棵家族樹中，最上面的“爺爺”是根，他的兒子是一級子節點，孫子是二級子節點，直到沒有子節點的“葉子”節點。
什麼是DFS？¶
DFS（Depth-First Search，深度優先搜索）是一種遍歷或搜索方法，核心思想是“一條路走到黑，走不通再回頭”。想象你在迷宮中探險，先選一條路往前走，直到無法繼續（比如遇到死衚衕），再回到岔路口選下一條路。這種“深入到底，再回溯”的方式，就是DFS的特點。
樹的DFS遍歷分類¶
在樹中，DFS遍歷通常分爲三種：前序遍歷（根→左→右）、中序遍歷（左→根→右）、後序遍歷（左→右→根）。其中，前序遍歷（根→左→右）最直接體現“從根到葉”的路徑，因爲它先訪問當前節點（根），再遞歸處理左子樹，最後處理右子樹，恰好覆蓋了從根到每個葉子的完整路徑。
遞歸實現前序遍歷（根到葉路徑）¶
遞歸是實現DFS的直觀方式，因爲它天然符合“深入子樹”的邏輯。以下是遞歸前序遍歷的步驟：
1. 訪問當前節點：先處理當前節點（例如打印節點值）；
2. 遞歸處理左子樹：如果有左子節點，遞歸執行前序遍歷；
3. 遞歸處理右子樹：如果有右子節點，遞歸執行前序遍歷。
示例：以一棵簡單二叉樹爲例（根爲1，左子樹2，右子樹3；2的左子樹4，右子樹5）：
1
/ \
2 3
/ \
4 5
遞歸過程：
- 訪問1 → 遞歸左子樹2 → 訪問2 → 遞歸左子樹4 → 訪問4（無左/右子樹，返回）→ 遞歸右子樹5 → 訪問5（無左/右子樹，返回）→ 遞歸右子樹3 → 訪問3（無左/右子樹，返回）。
- 最終訪問順序：1 → 2 → 4 → 5 → 3。
僞代碼（Python風格）：
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def dfs_preorder(node):
if node is None: # 空節點直接返回
return
print(node.val, end=" ") # 訪問當前節點
dfs_preorder(node.left) # 遞歸左子樹
dfs_preorder(node.right) # 遞歸右子樹
# 構建示例樹
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# 調用函數，輸出根到葉路徑
dfs_preorder(root) # 輸出：1 2 4 5 3
非遞歸實現前序遍歷（用棧）¶
遞歸需要調用函數自身，而DFS的“深度優先”也可以用棧來模擬（棧是“後進先出”的數據結構）。非遞歸前序遍歷的步驟：
1. 初始化棧：將根節點入棧；
2. 循環處理棧頂節點：
- 彈出棧頂節點，訪問它；
- 先右後左將子節點入棧（因爲棧“後進先出”，先入右子樹會導致左子樹先被彈出處理）；
3. 終止條件：棧爲空時遍歷結束。
僞代碼（Python風格）：
def dfs_preorder_iterative(root):
if root is None:
return
stack = [root] # 初始化棧，根節點入棧
while stack:
node = stack.pop() # 彈出棧頂節點
print(node.val, end=" ") # 訪問當前節點
# 先右後左入棧，保證左子樹先被處理
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
# 調用函數，輸出結果同上
dfs_preorder_iterative(root) # 輸出：1 2 4 5 3
爲什麼根到葉的遍歷重要？¶
根到葉的DFS遍歷是解決“路徑相關問題”的基礎，例如：
- 路徑求和：求所有根到葉路徑的和是否等於目標值；
- 路徑輸出：打印所有從根到葉的路徑（如示例中的1→2→4、1→2→5、1→3）；
- 最短路徑：在有權樹中，找到根到葉的最小/最大路徑和。
總結¶
DFS（深度優先搜索）的核心是“深入一條路徑，直到無法前進再回溯”。樹的前序遍歷是根到葉路徑的典型遍歷方式，遞歸實現簡單直觀，適合初學者理解；非遞歸實現用棧模擬遞歸過程，更適合處理大規模數據。掌握根到葉的DFS遍歷，能幫助我們解決路徑相關的算法問題，是數據結構中“樹”這一章節的核心技能。