20 | 理论讲解：二叉树遍历-算法面试通关 50 讲

当前位置:　首页>> 技术小册>> 算法面试通关 50 讲

### 20 | 理论讲解：二叉树遍历

在算法面试中，二叉树遍历是一个基础而又极其重要的知识点。它不仅考察了面试者对数据结构的基本理解，还涉及到了递归、迭代等多种编程技巧的应用。本章节将深入剖析二叉树的四种基本遍历方式：前序遍历（Preorder Traversal）、中序遍历（Inorder Traversal）、后序遍历（Postorder Traversal）以及层次遍历（Level-Order Traversal），并探讨它们各自的实现原理、应用场景及代码实现。

#### 20.1 二叉树基础

在正式开始讨论遍历之前，我们先简要回顾一下二叉树的基本概念。二叉树是一种特殊的树形结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树广泛应用于各种算法和数据结构中，如搜索树（如二叉搜索树）、堆、表达式树等。

#### 20.2 遍历的基本概念

二叉树的遍历是指按照某种特定的顺序访问树中的每个节点，且每个节点仅被访问一次。遍历是理解和操作二叉树的基础，不同的遍历方式能够反映出树中节点间的不同关系。

#### 20.3 前序遍历（Preorder Traversal）

前序遍历的访问顺序为：根节点 -> 左子树 -> 右子树。即首先访问根节点，然后递归地进行前序遍历左子树，最后递归地遍历右子树。前序遍历常用于需要首先处理根节点的场景，如复制树、计算树的高度等。

**递归实现**：

```python
def preorderTraversal(root):
    if root is None:
        return []
    result = [root.val]
    result.extend(preorderTraversal(root.left))
    result.extend(preorderTraversal(root.right))
    return result
```

**迭代实现**（使用栈）：

```python
def preorderTraversalIterative(root):
    if root is None:
        return []
    stack, result = [root], []
    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
```

#### 20.4 中序遍历（Inorder Traversal）

中序遍历的访问顺序为：左子树 -> 根节点 -> 右子树。它首先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。中序遍历在二叉搜索树（BST）中尤为重要，因为它能按升序访问所有节点。

**递归实现**：

```python
def inorderTraversal(root):
    if root is None:
        return []
    result = inorderTraversal(root.left)
    result.append(root.val)
    result.extend(inorderTraversal(root.right))
    return result
```

**迭代实现**（使用栈）：

```python
def inorderTraversalIterative(root):
    if root is None:
        return []
    stack, result = [], []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    return result
```

#### 20.5 后序遍历（Postorder Traversal）

后序遍历的访问顺序为：左子树 -> 右子树 -> 根节点。它首先递归地遍历左子树，然后递归地遍历右子树，最后访问根节点。后序遍历常用于需要最后处理根节点的场景，如计算树的深度、删除节点等。

**递归实现**：

```python
def postorderTraversal(root):
    if root is None:
        return []
    result = postorderTraversal(root.left)
    result.extend(postorderTraversal(root.right))
    result.append(root.val)
    return result
```

**迭代实现**（使用栈，需要额外的辅助标记或栈）：

```python
def postorderTraversalIterative(root):
    if root is None:
        return []
    stack, result = [root], []
    while stack:
        node = stack[-1]
        if (node.left is None and node.right is None) or (
            (node.right in stack) and (node.left is None or node.left in stack)
        ):
            result.append(stack.pop().val)
        else:
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
    return result
```

注意：后序遍历的迭代实现较为复杂，通常需要额外的数据结构（如标记节点是否已访问过的集合或栈）来辅助判断。

#### 20.6 层次遍历（Level-Order Traversal）

层次遍历也称为广度优先遍历（BFS），它按照从上到下、从左到右的顺序访问树的每个节点。层次遍历通常使用队列来实现。

**实现**：

```python
from collections import deque

def levelOrderTraversal(root):
    if root is None:
        return []
    queue, result = deque([root]), []
    while queue:
        node = queue.popleft()
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result
```

#### 20.7 总结与比较

- **前序遍历**：先根节点，后左右子树，常用于复制树、计算树的高度等。
- **中序遍历**：先左子树，后根节点，再右子树，在BST中可得到排序结果。
- **后序遍历**：先左右子树，后根节点，常用于计算树的深度、删除节点等。
- **层次遍历**：从上到下、从左到右遍历节点，常用于层次化展示或处理树形结构。

不同遍历方式的选择取决于具体问题的需求。掌握这四种遍历方式及其实现方法，对于理解和操作二叉树至关重要。在面试中，能够灵活运用这些遍历方法解决问题，将大大增强你的竞争力。

该分类下的相关小册推荐：

数据结构与算法(下)

数据结构与算法之美

编程之道-算法面试(下)

数据结构与算法(中)

业务开发实用算法精讲

数据结构与算法(上)

编程之道-算法面试(上)