前序遍历：递归与非递归实现

基本概念

前序遍历（Preorder Traversal） 是二叉树深度优先遍历（DFS）的一种。其访问顺序为：根结点 → 左子树 → 右子树。

  • 递归实现简洁直观，符合二叉树递归定义。
  • 非递归（迭代）实现需要显式使用栈模拟系统调用栈，避免递归深度过大导致的栈溢出。

算法步骤

  1. 递归版：
    • 若当前结点为空，直接返回。
    • 访问当前结点（如记录值）。
    • 递归遍历左子树。
    • 递归遍历右子树。
  2. 非递归版（栈）：
    • 初始化栈，将根结点压入栈中。
    • 循环直到栈为空：
      • 弹出栈顶结点，访问它。
      • 先将右孩子压栈（因为栈是后进先出，希望左孩子先被处理）。
      • 再将左孩子压栈。
    • 注意：压栈顺序为先右后左，则弹出顺序为先左后右，符合前序遍历要求。

内部实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from typing import List, Optional
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
# 递归实现
def preorderTraversal_recursive(root: Optional[TreeNode]) -> List[int]:
    res = []
    
    def preorder(node):
        if not node:
            return
        res.append(node.val)      # 根
        preorder(node.left)       # 左
        preorder(node.right)      # 右
    
    preorder(root)
    return res
# 非递归实现（栈）
def preorderTraversal_iterative(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
    res = []
    stack = [root]
    while stack:
        node = stack.pop()
        res.append(node.val)
        # 先右后左，保证左子树先出栈
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return res

复杂度分析

版本 时间复杂度 空间复杂度 说明
递归 O(n) O(h) h 为树高，最坏 O(n)（斜树），平均 O(log n)
非递归 O(n) O(h) 栈显式存储，最坏 O(n)
  • 时间复杂度：每个结点访问一次，O(n)。
  • 空间复杂度：取决于栈（递归或显式）的最大深度，即树高。平衡树为 O(log n)，斜树为 O(n)。

应用场景

  • 克隆/复制二叉树：前序遍历顺序（根→左→右）天然适合按结构拷贝。
  • 序列化与反序列化：前序遍历 + 空标记可以唯一重建二叉树（需配合中序或后序）。
  • 表达式树求值：前缀表达式（波兰表达式）可直接用前序遍历计算。
  • 目录结构打印：如 Linux tree 命令输出格式，先打印根（目录），再递归子目录。
  • 编译器语法树遍历：某些语法分析阶段采用前序生成中间代码。
  • 真实系统
    • 文件系统快照对比（先比较根元数据，再递归子目录）。
    • JSON/XML 解析器的深度优先遍历常采用前序逻辑。
    • Git 对象树的部分遍历也使用类似思想。

相关：