LeetCode 144：二叉树的前序遍历 | 递归与迭代

LeetCode 144：二叉树的前序遍历 | 递归与迭代

一、题目详解

1.1 题目描述

LeetCode 144：二叉树的前序遍历（Binary Tree Preorder Traversal）

给定一个二叉树的根节点root，返回它的前序遍历结果。

难度：Medium

示例 1：

输入：root = [1,null,2,3] 输出：[1,2,3]

示例 2：

输入：root = [] 输出：[]

示例 3：

输入：root = [1] 输出：[1]

1.2 题目分析

前序遍历的顺序是：根节点 -> 左子树 -> 右子树

这是二叉树遍历的三种基本方式之一（前序、中序、后序），掌握这三种遍历方式是学习树结构的基础。

二、算法实现

2.1 递归实现

递归是最直观的实现方式，利用函数调用栈来模拟遍历过程：

def preorderTraversal(root): 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. 递归处理右子树

2.2 迭代实现

使用显式栈来模拟递归调用：

def preorderTraversal_iterative(root): if not root: return [] result = [] stack = [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

迭代思路解析：

1. 初始化栈，将根节点入栈
2. 弹出栈顶节点，访问它
3. 将右子节点入栈（因为栈是LIFO，后处理）
4. 将左子节点入栈（先处理）
5. 重复直到栈为空

2.3 Morris遍历（O(1)空间复杂度）

这是一种不使用栈的遍历方法：

def preorderTraversal_morris(root): result = [] current = root while current: if not current.left: # 没有左子树，直接访问当前节点 result.append(current.val) current = current.right else: # 找到左子树的最右节点 predecessor = current.left while predecessor.right and predecessor.right != current: predecessor = predecessor.right if not predecessor.right: # 建立线索 predecessor.right = current result.append(current.val) current = current.left else: # 恢复树结构 predecessor.right = None current = current.right return result

三、复杂度分析

3.1 递归实现

• 时间复杂度：O(n)，每个节点访问一次
• 空间复杂度：O(h)，h为树的高度
  • 最好情况（平衡树）：O(log n)
  • 最坏情况（链式树）：O(n)

3.2 迭代实现

• 时间复杂度：O(n)，每个节点入栈出栈一次
• 空间复杂度：O(h)，栈的最大深度

3.3 Morris遍历

• 时间复杂度：O(n)，每个节点访问常数次
• 空间复杂度：O(1)，只使用常量额外空间

四、边界情况讨论

4.1 空树

root = None # 输出：[]

4.2 单节点树

root = TreeNode(1) # 输出：[1]

4.3 只有左子树

# 1 # / # 2 # / # 3 # 输出：[1, 2, 3]

4.4 只有右子树

# 1 # \ # 2 # \ # 3 # 输出：[1, 2, 3]

4.5 完全二叉树

# 1 # / \ # 2 3 # / \ / \ # 4 5 6 7 # 输出：[1, 2, 4, 5, 3, 6, 7]

五、实际应用场景

5.1 树的序列化

前序遍历常用于树的序列化操作：

def serialize(root): """将二叉树序列化为字符串""" result = [] def preorder(node): if not node: result.append("#") return result.append(str(node.val)) preorder(node.left) preorder(node.right) preorder(root) return ",".join(result)

5.2 表达式树求值

在前序表达式（波兰表达式）中，前序遍历可以用于求值：

# 表达式树： + # / \ # 3 * # / \ # 4 5 # 前序遍历：[+, 3, *, 4, 5] # 求值结果：3 + 4 * 5 = 23

5.3 文件系统遍历

在文件系统中，前序遍历对应深度优先搜索：

# 目录结构： # root/ # ├── docs/ # │ └── readme.txt # └── src/ # └── main.py # 前序遍历：[root, docs, readme.txt, src, main.py]

六、总结

6.1 核心要点

6.2 与其他遍历的对比

6.3 扩展思考

1. 如何在前序遍历中记录节点的深度信息？
2. 如何修改算法，同时输出节点的路径信息？
3. 前序遍历在哪些算法问题中是关键步骤？

参考资料：

• LeetCode 144 题解
• 二叉树遍历总结