【小白笔记】二叉树的前序，中序，后序，层序遍历（递归与迭代）

二叉树的遍历是树形结构中最基础的操作。所谓的**“前序遍历”**，其实是指“根节点”相对于左右子树的访问顺序。

1. 记住口诀：根 -> 左 -> 右

前序遍历（Pre-order Traversal）的逻辑非常固定：

1. 首先访问根节点 (Root)。
2. 然后递归地访问左子树 (Left)。
3. 最后递归地访问右子树 (Right)。

2. 解法一：递归法（最直观）

递归是最符合树定义的方法，因为树本身就是递归定义的。

classSolution:defpreorderTraversal(self,root:Optional[TreeNode])->List[int]:res=[]defdfs(node):ifnotnode:return# 1. 根：先记录当前节点的值res.append(node.val)# 2. 左：递归遍历左子树dfs(node.left)# 3. 右：递归遍历右子树dfs(node.right)dfs(root)returnres

3. 解法二：迭代法（利用栈 Stack）

在面试中，面试官经常会问：“如果不让你用递归，你怎么实现？”
这时我们需要模拟递归的过程。递归本质上是利用了系统的调用栈，所以我们可以手动维护一个栈 (Stack)。

关键点：栈是“后进先出”的。为了保证“先左后右”的访问顺序，我们在压栈时要先压右子树，再压左子树。

classSolution:defpreorderTraversal(self,root:Optional[TreeNode])->List[int]:ifnotroot:return[]stack=[root]res=[]whilestack:# 弹出栈顶节点（当前的“根”）node=stack.pop()res.append(node.val)# 先把右孩子放进去（后出）ifnode.right:stack.append(node.right)# 再把左孩子放进去（先出）ifnode.left:stack.append(node.left)returnres

4. 总结与对比

• 前序遍历：根 -> 左 -> 右
• 中序遍历：左 -> 根 -> 右（145 题）
• 后序遍历：左 -> 右 -> 根（94 题）

为什么迭代法里要先压right？
因为我们想要先处理left。在栈结构里，最后放进去的东西会最先被弹出来。所以，先把右边的“存着”，处理完左边那一条线后，再回来处理右边。

复杂度分析

• 时间复杂度：O ( n ) O(n)O(n)。每个节点都被访问且仅访问一次。
• 空间复杂度：O ( n ) O(n)O(n)。最坏情况下（树呈链状），递归栈或手动栈的深度会达到n nn。

中序遍历（In-order Traversal）是二叉树最常用的遍历方式之一，特别是在**二叉搜索树（BST）**中，中序遍历的结果恰好是升序排列的。

1. 记住口诀：左 -> 根 -> 右

中序遍历的逻辑顺序是：

1. 首先递归地访问左子树 (Left)。
2. 然后访问根节点 (Root)。
3. 最后递归地访问右子树 (Right)。

2. 解法一：递归法（极其简单）

你只需要在“前序遍历”的基础上，把记录值的语句res.append挪到两次递归调用中间即可。

classSolution:definorderTraversal(self,root:Optional[TreeNode])->List[int]:res=[]defdfs(node):ifnotnode:return# 1. 左：一直往左走dfs(node.left)# 2. 根：走不动了再记录当前值res.append(node.val)# 3. 右：最后看右边dfs(node.right)dfs(root)returnres

3. 解法二：迭代法（面试重点）

迭代法实现中序遍历比前序遍历稍微复杂一点，因为访问节点的顺序和处理节点的顺序是不一致的。我们需要先“潜入”到最左端的叶子节点。

逻辑：

1. 一路向左：只要当前节点不为空，就把它压入栈，并继续往左走。
2. 弹出并记录：左边走到底了，从栈中弹出一个节点（这就是当前的“根”），记录它的值。
3. 转向右边：处理完根节点后，把指针指向它的右孩子，重复上述过程。

classSolution:definorderTraversal(self,root:Optional[TreeNode])->List[int]:res=[]stack=[]curr=root# curr 不为空或者栈不为空，就继续whilecurrorstack:# 步骤 1：一路向左扎到底whilecurr:stack.append(curr)curr=curr.left# 步骤 2：弹出栈顶元素（最左或最近的根）curr=stack.pop()res.append(curr.val)# 步骤 3：转向右子树curr=curr.rightreturnres

4. 为什么中序遍历很重要？

• 排序属性：如果你对一棵“二叉搜索树”进行中序遍历，得到的结果一定是从小到大排好序的数组。
• 验证搜索树：判断一棵树是否是二叉搜索树（LeetCode 98），最简单的方法就是看它的中序遍历是否是递增的。

总结三种遍历的递归区别：

• 前序：记录-> 左 -> 右（先看到根，再看子树）
• 中序：左 ->记录-> 右（先看完左边，回头看根，再看右边）
• 后序：左 -> 右 ->记录（最后才看根，常用于计算树的高度或删除树）

后序遍历（Post-order Traversal）是三种遍历中最“内敛”的一种。它的特点是：必须等左右子树全部处理完，才处理根节点。

1. 记住口诀：左 -> 右 -> 根

后序遍历的逻辑顺序是：

1. 首先递归地访问左子树 (Left)。
2. 然后递归地访问右子树 (Right)。
3. 最后访问根节点 (Root)。

2. 解法一：递归法

依然是那三行核心代码，只是顺序变了。它是计算树的高度（104题）或删除整棵树时的标准做法。

classSolution:defpostorderTraversal(self,root:Optional[TreeNode])->List[int]:res=[]defdfs(node):ifnotnode:returndfs(node.left)# 1. 左dfs(node.right)# 2. 右res.append(node.val)# 3. 根dfs(root)returnres

3. 解法二：迭代法（“偷懒”镜像反转法）

后序遍历的迭代法如果正着写非常复杂，因为你需要判断右子树是否已经访问过。但有一个神级脑筋急转弯：

• 前序遍历是：根 -> 左 -> 右
• 如果我们稍微改下顺序，写成：根 -> 右 -> 左
• 把这个结果整体反转 (Reverse)，就会得到：左 -> 右 -> 根——这正是后序遍历！

classSolution:defpostorderTraversal(self,root:Optional[TreeNode])->List[int]:ifnotroot:return[]stack=[root]res=[]# 按照 根 -> 右 -> 左 的顺序入栈whilestack:node=stack.pop()res.append(node.val)# 因为是栈，先压左，后压右，弹出来的就是先右后左ifnode.left:stack.append(node.left)ifnode.right:stack.append(node.right)# 最后把 [根, 右, 左] 反转成 [左, 右, 根]returnres[::-1]

4. 为什么后序遍历很有用？

后序遍历体现了**“自底向上”**的思想。

• 计算树的高度：你需要知道左子树多高，右子树多高，然后取最大值加 1（根节点）。
• 计算子树节点和：你必须先算出左右两边的和，才能算出包含当前根的总和。
• 最近公共祖先 (LCA)：通过后序遍历向上回溯信息。

三种遍历的直观总结

想象一棵树，你拿着一支笔沿着树的外围轮廓走一圈（从根左侧出发，绕一圈回到根右侧）：

1. 前序遍历：在经过节点的左侧时记录它。
2. 中序遍历：在经过节点的底部时记录它。
3. 后序遍历：在经过节点的右侧时记录它。

知识点大串联

到目前为止，我们已经横跨了三个大领域：

1. 线性结构：链表（双指针、快慢指针）、数组（滑动窗口、原地翻转）。
2. 数学模拟：大数加法（进位处理、补零逻辑）。
3. 树形结构：二叉树（前中后序递归与迭代）。

发现**“栈 (Stack)”和“递归”**其实是双胞胎

层序遍历（Level-order Traversal）与之前的前、中、后序遍历完全不同。前三种属于深度优先遍历（DFS），而层序遍历属于广度优先遍历（BFS）。

它像剥洋葱一样，从根节点开始，一层一层地由上到下、由左到右访问所有节点。

1. 核心工具：队列（Queue）

实现层序遍历的关键在于使用“队列”这种先进先出（FIFO）的数据结构：

1. 入队：把根节点放进队列。
2. 循环：只要队列不为空：
   • 记录当前层的节点个数（确定这层有多少人）。
   • 依次弹出这些节点。
   • 把它们的左、右孩子（如果有）依次加入队列末尾。

2. 代码实现 (Python)

fromcollectionsimportdequeclassSolution:deflevelOrder(self,root:Optional[TreeNode])->List[List[int]]:ifnotroot:return[]res=[]# 使用 deque（双端队列），popleft() 的时间复杂度为 O(1)queue=deque([root])whilequeue:# 1. 确定当前层有多少个节点level_size=len(queue)current_level=[]# 2. 连续处理 level_size 个节点，保证它们属于同一层for_inrange(level_size):node=queue.popleft()current_level.append(node.val)# 3. 将下一层的孩子节点加入队列ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)# 4. 将这一层的结果加入大列表res.append(current_level)returnres

3. 为什么需要level_size = len(queue)？

这是层序遍历最关键的一步。

• 因为队列在不断地添加新节点（下一层的孩子），如果不提前固定当前层的数量，while循环就会一直跑下去，你无法区分哪些节点属于第一层，哪些属于第二层。
• 通过len(queue)，我们给当前层画了一个“圈”，保证for循环只处理这一层的节点。

4. 复杂度分析

• 时间复杂度：O ( N ) O(N)O(N)。每个节点入队和出队各一次。
• 空间复杂度：O ( N ) O(N)O(N)。在最坏情况下（比如满二叉树），最后一层的节点数大约是N / 2 N/2N/2，队列需要存储这些节点。

5. 常见变形题

层序遍历的模版非常强大，稍微改动就能解决很多问题：

1. 二叉树的最大深度：层序遍历跑了多少个while循环，深度就是多少。
2. 二叉树的右视图：每一层for循环结束时的最后一个节点，就是从右边看到的节点。
3. 之字形遍历：根据层数的奇偶性，反转current_level列表。

总结：DFS vs BFS