python二叉樹的前序遍歷怎么理解

# Python二叉樹的前序遍歷怎么理解

## 什么是二叉樹的前序遍歷

二叉樹的前序遍歷（Preorder Traversal）是樹結構中最基礎的遍歷方式之一，其核心特點是按照**根節點→左子樹→右子樹**的順序訪問每個節點。這種"根優先"的策略使得前序遍歷在需要優先處理父節點的場景中非常有用。

### 遍歷順序的直觀理解

想象你正在探索一個家族樹：
1. 首先訪問當前家族的代表（根節點）
2. 然后探索他的左側后代（左子樹）
3. 最后探索右側后代（右子樹）

這種"自上而下"的訪問順序正是前序遍歷的典型特征。

## 前序遍歷的遞歸實現

遞歸實現是最直觀的表達方式，完美體現了"分而治之"的算法思想。

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorderTraversal(root: TreeNode) -> list:
    result = []
    def traverse(node):
        if not node:
            return
        result.append(node.val)  # 訪問根節點
        traverse(node.left)      # 遍歷左子樹
        traverse(node.right)     # 遍歷右子樹
    traverse(root)
    return result

遞歸調用棧分析

當處理如下二叉樹時：

    1
   / \
  2   3
 / \
4   5

遞歸調用的堆棧變化： 1. 訪問1，結果[1] 2. 遞歸左子樹2，結果[1,2] 3. 遞歸4，結果[1,2,4] 4. 返回至2，訪問右5，結果[1,2,4,5] 5. 返回至1，訪問右3，結果[1,2,4,5,3]

前序遍歷的迭代實現

雖然遞歸簡潔，但理解迭代實現能加深對遍歷過程的認識。我們需要顯式地使用棧來模擬遞歸的調用過程。

def preorderTraversalIterative(root: TreeNode) -> list:
    if not root:
        return []
    
    stack = [root]
    result = []
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        # 注意右子樹先入棧（后出）
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result

迭代過程演示

同樣以之前的二叉樹為例：

前序遍歷的應用場景

1. 目錄結構打印

非常適合需要先顯示父目錄再顯示子目錄的場景

def printDirectory(node, indent=""):
    if not node:
        return
    print(indent + str(node.val))
    printDirectory(node.left, indent + "  ")
    printDirectory(node.right, indent + "  ")

2. 表達式樹求值

前序遍歷天然適合前綴表達式（波蘭表達式）的生成

    +
   / \
  *   3
 / \
2   4

前序遍歷結果：+ * 2 4 3

3. 樹的克隆

在克隆樹結構時，需要先創建父節點再創建子節點

時間復雜度分析

無論是遞歸還是迭代實現，前序遍歷的時間復雜度都是O(n)，其中n是樹中節點的數量，因為每個節點恰好被訪問一次。

空間復雜度方面： - 遞歸實現：O(h)，h為樹的高度（遞歸調用棧的深度） - 迭代實現：O(h)，由顯式棧的大小決定

對于傾斜樹（退化為鏈表）的情況，空間復雜度最差為O(n)。

常見問題解答

Q1: 前序遍歷和中序/后序遍歷的主要區別？

• 前序：根→左→右
• 中序：左→根→右
• 后序：左→右→根

Q2: 為什么迭代實現要右子樹先入棧？

因為棧是LIFO結構，我們需要保證左子樹先出棧，所以要讓右子樹先入棧。

Q3: 如何用前序遍歷結果重建二叉樹？

需要配合中序遍歷結果才能唯一確定二叉樹結構。單獨的前序結果可能有多種樹形對應。

總結

理解前序遍歷的關鍵在于把握”根優先”的原則。通過遞歸實現可以直觀理解遍歷的本質，而迭代實現則揭示了底層的工作機制。掌握前序遍歷不僅有助于解決樹結構相關問題，也是理解更復雜算法（如DFS）的重要基礎。建議讀者可以嘗試用前序遍歷解決LeetCode上的相關題目（如144題）來加深理解。 “`