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递归思路解析如果当前节点为空直接返回访问当前节点将值加入结果列表递归处理左子树递归处理右子树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迭代思路解析初始化栈将根节点入栈弹出栈顶节点访问它将右子节点入栈因为栈是LIFO后处理将左子节点入栈先处理重复直到栈为空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 235.3 文件系统遍历在文件系统中前序遍历对应深度优先搜索# 目录结构 # root/ # ├── docs/ # │ └── readme.txt # └── src/ # └── main.py # 前序遍历[root, docs, readme.txt, src, main.py]六、总结6.1 核心要点要点说明遍历顺序根 → 左 → 右递归实现简洁直观容易理解迭代实现使用栈模拟递归适合处理大规模数据Morris遍历O(1)空间复杂度适合内存受限场景6.2 与其他遍历的对比遍历方式顺序特点前序根→左→右适合复制树、序列化中序左→根→右BST中得到有序序列后序左→右→根适合释放资源、计算子树信息层序按层访问适合求树的深度、宽度优先搜索6.3 扩展思考如何在前序遍历中记录节点的深度信息如何修改算法同时输出节点的路径信息前序遍历在哪些算法问题中是关键步骤参考资料LeetCode 144 题解二叉树遍历总结