二叉树的前序遍历实现

题目

二叉树的前序遍历实现

信息

• 类型：问答
• 难度：⭐

考点

二叉树遍历,递归算法,基本数据结构操作

快速回答

二叉树前序遍历按照根节点→左子树→右子树的顺序访问节点。核心实现方式：

• 递归法：直接遵循遍历定义实现
• 迭代法：使用栈模拟递归过程

时间复杂度 O(n)，空间复杂度 O(h)（h为树高）

解析

原理说明

前序遍历（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 preorder_recursive(root):
    res = []
    def traverse(node):
        if not node: return
        res.append(node.val)  # 先访问根节点
        traverse(node.left)   # 再遍历左子树
        traverse(node.right)  # 最后遍历右子树
    traverse(root)
    return res

# 迭代实现（使用栈）
def preorder_iterative(root):
    res = []
    stack = [root]
    while stack:
        node = stack.pop()
        if node:
            res.append(node.val)        # 访问根节点
            stack.append(node.right)    # 右子节点先入栈
            stack.append(node.left)     # 左子节点后入栈（保证先出）
    return res

最佳实践

• 递归选择：代码简洁但可能栈溢出，适合小规模树
• 迭代选择：显式栈避免递归开销，适合大规模数据
• 终止条件：必须检查节点是否为 null
• 结果存储：使用列表动态记录访问顺序

常见错误

• 忘记检查空节点导致 NullPointerException
• 错误顺序：将根节点访问放在子树遍历之后
• 迭代法中压栈顺序错误（必须先右后左）
• 修改原始树结构（如未克隆直接修改）

扩展知识

• 遍历变种：中序（左→根→右）、后序（左→右→根）
• Morris遍历：O(1) 空间复杂度的前序遍历算法
• 应用场景：表达式树求值、目录结构打印、克隆二叉树
• 相关算法：DFS（深度优先搜索）是前序遍历的推广形式