1. 从“遍历”说起为什么二叉树遍历是程序员的必修课如果你刚开始接触数据结构或者正在准备技术面试那么“二叉树遍历”这个词你肯定绕不过去。它听起来有点枯燥不就是把树里的节点都访问一遍吗但恰恰是这个看似基础的操作是理解递归、栈、队列乃至更复杂算法如动态规划、回溯的绝佳切入点。很多人在学习时只是机械地背下了“前序、中序、后序”这几个名字和代码却很少去深究为什么是这三种顺序它们各自解决了什么问题在实际写代码时除了递归我们还能怎么玩今天我们不谈空泛的理论就从最接地气的角度把二叉树的前序、中序、后序遍历掰开揉碎了讲清楚。我会结合具体的代码示例以Python为主思路通用、面试中高频的变形题以及我在实际开发和刷题中踩过的坑让你不仅知道怎么写更明白为什么要这么写以及遇到各种“幺蛾子”时该怎么处理。简单来说遍历一棵二叉树就是按照某种规则不重复地访问树中的每一个节点。而前序、中序、后序指的就是访问根节点的时机相对于访问其左右子树的时机。记住这个核心后面的一切都迎刃而解。2. 三种遍历的“灵魂”访问根节点的时机这是理解三种遍历最本质、也最不容易混淆的角度。我们先把二叉树抽象成一个最简单的单元一个根节点Root带着它的左子树Left Subtree和右子树Right Subtree。前序遍历Preorder Traversal根- 左 - 右。你首先处理当前这个“根”节点然后再去处理它的左半边天下左子树最后处理右半边天下右子树。这是一种“自上而下”的天然顺序。中序遍历Inorder Traversal左 -根- 右。你先彻底探索完左子树然后回来处理根节点最后再去探索右子树。对于二叉搜索树BST来说这个顺序会产生一个递增的序列这是它最重要的特性。后序遍历Postorder Traversal左 - 右 -根。你把左右两边的“家务事”都处理干净了最后再来处理根节点。这种顺序在需要先子节点、后父节点的场景下非常有用比如计算子树的高度、释放树的内存。很多人靠死记硬背“前中后”对应“根左右、左根右、左右根”但更容易混淆。我的建议是永远用**“根节点的访问时机”**来记忆前序就是最先访问根中序就是中间访问根后序就是最后访问根。左右子树的访问顺序永远是先左后右除非题目特殊要求这是约定俗成的。为了更直观我们看一个具体的二叉树例子1 / \ 2 3 / \ \ 4 5 6前序遍历结果1, 2, 4, 5, 3, 6。 验证先访问根1然后遍历左子树(2,4,5)最后遍历右子树(3,6)。在遍历左子树时以2为根同样遵循“根左右”所以是2,4,5。中序遍历结果4, 2, 5, 1, 3, 6。 验证先遍历左子树(4,2,5)然后访问根1最后遍历右子树(3,6)。左子树的中序遍历是4,2,5。后序遍历结果4, 5, 2, 6, 3, 1。 验证先遍历左子树(4,5,2)然后遍历右子树(6,3)最后访问根1。3. 递归实现最直观的“分治”思想递归是实现这三种遍历最符合直觉、代码也最简洁的方式。它完美体现了“分而治之”的思想要遍历整棵树我先访问根节点根据时机不同然后把遍历左子树和右子树的任务分别看作两个规模更小的、完全相同的遍历问题。下面是用Python定义的经典二叉树节点以及三种遍历的递归实现class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def preorder_recursive(root, result): 前序遍历递归 if not root: return result.append(root.val) # 访问根节点 preorder_recursive(root.left, result) # 遍历左子树 preorder_recursive(root.right, result) # 遍历右子树 def inorder_recursive(root, result): 中序遍历递归 if not root: return inorder_recursive(root.left, result) # 遍历左子树 result.append(root.val) # 访问根节点 inorder_recursive(root.right, result) # 遍历右子树 def postorder_recursive(root, result): 后序遍历递归 if not root: return postorder_recursive(root.left, result) # 遍历左子树 postorder_recursive(root.right, result) # 遍历右子树 result.append(root.val) # 访问根节点递归实现的要点与坑点递归终止条件if not root: return。这是最重要的没有它就会无限递归下去。它对应着走到了空节点意味着当前这条分支已经探索完毕。参数传递result列表作为一个“全局”记录者在递归过程中不断被修改。你也可以让递归函数直接返回一个列表但那样在拼接列表时会产生额外的空间开销。面试时两种写法都要会通常传递一个引用更高效。空间复杂度递归调用需要使用系统栈空间复杂度与树的高度成正比。在最坏情况树退化成一条链下空间复杂度是O(N)。这是递归方法的主要缺点。踩坑实录很多新手在写递归时容易在result.append(root.val)这一行犯错比如忘记append或者错误地return result.append(...)append方法返回None。记住递归函数的目的是“完成任务”遍历并收集而不是“返回结果”除非是自底向上的计算。另外一定要先判断root是否为空否则访问root.val会直接导致AttributeError。4. 迭代实现手动模拟栈理解递归的本质递归虽然简洁但有时我们需要更精细地控制遍历过程或者担心递归深度过深导致栈溢出。这时迭代法就派上用场了。迭代法的核心是用我们自己的栈Stack来模拟系统调用栈的过程。迭代法比递归难理解一些因为我们需要手动管理节点的访问和压栈顺序。三种遍历的迭代写法各有特点尤其是中序遍历与前序/后序有显著不同。4.1 前序遍历的迭代实现前序遍历是“根左右”迭代的思路很直接先把根节点压入栈。循环条件栈不为空。弹出栈顶节点并访问它这就是“根”。因为栈是“后进先出”为了保证接下来先处理左子树再处理右子树即“左右”的顺序我们需要先将右孩子压栈再将左孩子压栈。这样弹出时就会先弹出左孩子。def preorder_iterative(root): 前序遍历迭代 if not root: return [] stack, result [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 result4.2 中序遍历的迭代实现中序遍历是“左根右”不能像前序那样简单。我们需要用一个指针curr来模拟“一路向左到底”的过程同时用栈来保存“回退”的路径。从根节点开始当前节点curr不为空就将其压栈然后curr指向左孩子。这相当于深入左子树。当curr为空时说明已经走到最左下了。此时从栈中弹出节点这就是当前子树的“根”访问它。访问完后将curr指向该节点的右孩子开始处理右子树。重复上述过程。def inorder_iterative(root): 中序遍历迭代 stack, result, curr [], [], root while curr or stack: # 一路向左把节点压入栈 while curr: stack.append(curr) curr curr.left # 弹出栈顶节点并访问 curr stack.pop() result.append(curr.val) # 访问根节点 # 转向右子树 curr curr.right return result4.3 后序遍历的迭代实现后序遍历是“左右根”。我们可以利用前序遍历“根左右”的迭代版本稍作修改。前序是“根左右”如果我们改成“根右左”然后将结果反转不就得到“左右根”了吗这是一个非常巧妙的技巧。模仿前序遍历但调整左右子节点入栈顺序得到“根右左”的访问序列。将得到的序列反转。def postorder_iterative(root): 后序遍历迭代- 修改前序法 if not root: return [] stack, result [root], [] while stack: node stack.pop() result.append(node.val) # 访问“根” # 注意这里左孩子先入栈右孩子后入栈 # 以保证出栈顺序是“根 - 右 - 左” if node.left: stack.append(node.left) if node.right: stack.append(node.right) # 将“根右左”的结果反转得到“左右根” return result[::-1]迭代实现的要点与坑点前序最简单理解“右先左后”的压栈顺序是关键。中序最经典while curr or stack这个循环条件要记牢。内层的while curr负责向左深入外层的循环负责处理栈和右子树。后序取巧但有效理解其本质是对前序的变形和反转。面试时如果要求写非递归后序这种方法通常是可以接受的。当然也有更接近递归逻辑的双栈法但理解起来更复杂。空节点处理迭代法中对于空树的判断if not root依然重要。在中序遍历中curr初始化为root即使root为空while curr or stack也能正确处理。实操心得我强烈建议在理解递归的基础上亲手画图模拟一遍迭代法的执行过程。拿一张纸画一个简单的二叉树然后一步步模拟栈的变化和curr指针的移动。这个过程能极大地加深你对遍历顺序和栈这个数据结构作用的理解。面试时如果被问到“不用递归怎么做”你能清晰地画出这个过程比干巴巴地背代码要加分得多。5. 莫里斯遍历一种空间复杂度为O(1)的神奇方法无论是递归还是迭代我们都需要O(H)的额外空间H为树高。有没有可能只用常数空间呢有这就是莫里斯遍历Morris Traversal。它的核心思想是利用树中大量的空指针临时将当前节点的前驱节点中序遍历下的前一个节点的右孩子指向自己从而在遍历完左子树后能通过这个临时链接返回到根节点省去了栈的空间。莫里斯遍历主要应用于中序遍历它稍微修改后也能用于前序。后序的莫里斯遍历非常复杂一般不要求掌握。我们重点看中序。算法步骤中序莫里斯遍历初始化curr指向根节点。当curr不为空时 a. 如果curr没有左孩子则访问curr并将curr指向其右孩子。 b. 如果curr有左孩子 i. 找到curr在中序遍历下的前驱节点pre。即curr左子树中最右边的那个节点。 ii. 如果pre的右孩子为空将其右孩子设置为curr建立临时链接然后将curr指向其左孩子。 iii. 如果pre的右孩子已经是curr说明左子树已被遍历过则断开这个临时链接将pre.right置为None访问curr然后将curr指向其右孩子。def inorder_morris(root): 中序遍历莫里斯 - 空间O(1) result [] curr root while curr: if not curr.left: # 如果没有左孩子直接访问当前节点然后转向右孩子 result.append(curr.val) curr curr.right else: # 找到当前节点在中序遍历下的前驱节点 pre curr.left while pre.right and pre.right ! curr: pre pre.right if not pre.right: # 建立临时链接指向当前节点 pre.right curr curr curr.left else: # 临时链接已存在说明左子树已遍历完 pre.right None # 恢复树的结构 result.append(curr.val) curr curr.right return result莫里斯遍历的优缺点优点空间复杂度为O(1)对于内存严格受限的环境或巨型二叉树有优势。缺点修改了树的结构尽管是临时的。这在多线程环境或不允许修改原数据的场景下是致命的。同时代码逻辑比递归和迭代复杂容易出错。注意事项除非面试官明确要求或者问题有严格的O(1)空间限制否则在工程实践中优先使用递归或迭代法。莫里斯遍历更像一种炫技的算法用于展示对遍历过程的深刻理解。一定要在代码注释中写明它修改了树的结构。6. 层序遍历另一种维度的遍历方式虽然标题聚焦于前中后序但相关热词中频繁出现“层序遍历”它同样至关重要。层序遍历不属于深度优先搜索DFS的范畴而是**广度优先搜索BFS**在树上的应用。它按照树的层级从上到下、从左到右访问节点。实现层序遍历的核心数据结构是队列Queue。将根节点放入队列。当队列不为空时 a. 记录当前队列的长度level_size即当前层的节点数。 b. 循环level_size次每次从队列中取出一个节点访问并将其非空的左右子节点依次加入队列。 c. 当前层所有节点处理完毕结果中保存当前层的节点值列表然后继续下一层。from collections import deque def level_order_traversal(root): 层序遍历 if not root: return [] result [] queue deque([root]) while queue: level_size len(queue) current_level [] for _ in range(level_size): node queue.popleft() current_level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) return result对于之前的例子树层序遍历的结果是[[1], [2, 3], [4, 5, 6]]。层序遍历的妙用求二叉树的最大宽度在遍历每一层时记录该层的节点数取最大值。找到二叉树每层的最大值。判断是否是完全二叉树在层序遍历中如果遇到一个空节点之后又遇到了非空节点则不是完全二叉树。锯齿形Z字型层序遍历偶数层将结果反转即可。7. 遍历序列的威力重构二叉树与解决实际问题知道怎么遍历还不够更重要的是能利用遍历序列解决问题。一个经典面试题是已知两种遍历序列能否唯一确定一棵二叉树前序 中序可以唯一确定。原理前序序列的第一个元素一定是根节点。在中序序列中找到这个根节点其左边就是左子树的中序序列右边就是右子树的中序序列。根据左右子树的节点数量可以在前序序列中划分出左右子树的前序序列。递归进行即可。后序 中序可以唯一确定。原理后序序列的最后一个元素一定是根节点。后续步骤与前序中序类似。前序 后序一般不能唯一确定除非是满二叉树或真二叉树。因为无法区分左右子树的边界。重构二叉树的代码示例前序中序def build_tree(preorder, inorder): 根据前序和中序遍历序列构建二叉树 if not preorder or not inorder: return None # 前序第一个是根节点 root_val preorder[0] root TreeNode(root_val) # 在中序中找到根节点的位置 root_index_in_inorder inorder.index(root_val) # 划分左右子树的中序序列 left_inorder inorder[:root_index_in_inorder] right_inorder inorder[root_index_in_inorder 1:] # 划分左右子树的前序序列长度与中序子树相同 left_preorder preorder[1:1 len(left_inorder)] right_preorder preorder[1 len(left_inorder):] # 递归构建 root.left build_tree(left_preorder, left_inorder) root.right build_tree(right_preorder, right_inorder) return root避坑指南上面的代码为了清晰使用了list.index()和列表切片这在递归过程中会创建大量新列表空间效率不高。在面试或性能要求高的场景下应该使用索引指针来避免复制。即传递(pre_start, pre_end, in_start, in_end)这样的参数范围在原始数组上操作。8. 遍历的应用场景与高频面试题变形最后我们来聊聊遍历在实战和面试中的具体应用。死记硬背代码没用关键是理解每种遍历顺序带来的特性。前序遍历的应用复制一棵树先创建根节点再递归复制左右子树。这天然符合前序顺序。序列化二叉树如JSON化将树的结构转化为字符串或数组前序是一种很直观的方式。求从根到叶子的所有路径在深度优先遍历中前序顺序可以方便地在向下探索时记录路径。中序遍历的应用二叉搜索树BST的相关操作这是中序遍历的“主场”。BST的中序遍历结果是一个升序数组。利用这个特性可以验证一棵树是否是BST。在BST中查找第K小的元素。恢复一棵出错的BST两个节点被错误交换。表达式树求值对于表达式树运算符是根操作数是叶子中序遍历能得到中缀表达式可能需要加括号。后序遍历的应用释放二叉树内存必须先释放左右子树才能释放根节点。C/C中的free或delete操作。计算二叉树的高度/深度树的高度 1 max(左子树高度 右子树高度)。这需要先知道子树高度是典型的后序逻辑。判断一棵树是否是平衡二叉树在计算高度的同时判断平衡性。计算二叉树中任意两个节点的最近公共祖先LCA一种经典的递归解法就是后序遍历。路径总和问题判断是否存在从根到叶子节点路径和等于目标值虽然前序也能做但后序在回溯时撤销状态更清晰。层序遍历的应用寻找二叉树的最大/最小深度。寻找二叉树每层的最大值/平均值。二叉树的右视图/左视图即每一层最右边/最左边的节点。判断是否是完全二叉树。一道经典变形题迭代版后序遍历的另一种写法双栈法前面提到了修改前序反转的方法这里介绍更直观的双栈法它模拟了“左右根”的访问顺序更容易理解后序的本质。使用栈s1先将根节点压入。循环从s1弹出节点将其压入另一个栈s2。然后将该节点的左孩子、右孩子如果存在依次压入s1。重复步骤2-3直到s1为空。此时s2中节点的出栈顺序就是后序遍历顺序。def postorder_iterative_two_stack(root): 后序遍历迭代 - 双栈法 if not root: return [] s1, s2 [root], [] result [] while s1: node s1.pop() s2.append(node) if node.left: s1.append(node.left) if node.right: s1.append(node.right) while s2: result.append(s2.pop().val) return result这个方法的妙处在于s1的压栈顺序是“根 - 右 - 左”弹出压入s2后s2的压栈顺序是“左 - 右 - 根”最后从s2弹出时自然就是“左右根”。它虽然用了两个栈但逻辑非常清晰。遍历二叉树远不止前中后序这三种方式它们是理解树形结构操作的基石。从递归到迭代从栈到队列再到莫里斯遍历的奇技淫巧每一种实现都在加深我们对程序控制流和数据结构的理解。下次当你再看到遍历相关的题目时不妨先问自己这个问题需要以什么样的顺序访问节点是父节点优先前序是子节点优先后序还是需要按层级处理层序想清楚了这一点选择何种遍历方法以及采用递归还是迭代就都有了明确的依据。
1. 从“遍历”说起为什么二叉树遍历是程序员的必修课如果你刚开始接触数据结构或者正在准备技术面试那么“二叉树遍历”这个词你肯定绕不过去。它听起来有点枯燥不就是把树里的节点都访问一遍吗但恰恰是这个看似基础的操作是理解递归、栈、队列乃至更复杂算法如动态规划、回溯的绝佳切入点。很多人在学习时只是机械地背下了“前序、中序、后序”这几个名字和代码却很少去深究为什么是这三种顺序它们各自解决了什么问题在实际写代码时除了递归我们还能怎么玩今天我们不谈空泛的理论就从最接地气的角度把二叉树的前序、中序、后序遍历掰开揉碎了讲清楚。我会结合具体的代码示例以Python为主思路通用、面试中高频的变形题以及我在实际开发和刷题中踩过的坑让你不仅知道怎么写更明白为什么要这么写以及遇到各种“幺蛾子”时该怎么处理。简单来说遍历一棵二叉树就是按照某种规则不重复地访问树中的每一个节点。而前序、中序、后序指的就是访问根节点的时机相对于访问其左右子树的时机。记住这个核心后面的一切都迎刃而解。2. 三种遍历的“灵魂”访问根节点的时机这是理解三种遍历最本质、也最不容易混淆的角度。我们先把二叉树抽象成一个最简单的单元一个根节点Root带着它的左子树Left Subtree和右子树Right Subtree。前序遍历Preorder Traversal根- 左 - 右。你首先处理当前这个“根”节点然后再去处理它的左半边天下左子树最后处理右半边天下右子树。这是一种“自上而下”的天然顺序。中序遍历Inorder Traversal左 -根- 右。你先彻底探索完左子树然后回来处理根节点最后再去探索右子树。对于二叉搜索树BST来说这个顺序会产生一个递增的序列这是它最重要的特性。后序遍历Postorder Traversal左 - 右 -根。你把左右两边的“家务事”都处理干净了最后再来处理根节点。这种顺序在需要先子节点、后父节点的场景下非常有用比如计算子树的高度、释放树的内存。很多人靠死记硬背“前中后”对应“根左右、左根右、左右根”但更容易混淆。我的建议是永远用**“根节点的访问时机”**来记忆前序就是最先访问根中序就是中间访问根后序就是最后访问根。左右子树的访问顺序永远是先左后右除非题目特殊要求这是约定俗成的。为了更直观我们看一个具体的二叉树例子1 / \ 2 3 / \ \ 4 5 6前序遍历结果1, 2, 4, 5, 3, 6。 验证先访问根1然后遍历左子树(2,4,5)最后遍历右子树(3,6)。在遍历左子树时以2为根同样遵循“根左右”所以是2,4,5。中序遍历结果4, 2, 5, 1, 3, 6。 验证先遍历左子树(4,2,5)然后访问根1最后遍历右子树(3,6)。左子树的中序遍历是4,2,5。后序遍历结果4, 5, 2, 6, 3, 1。 验证先遍历左子树(4,5,2)然后遍历右子树(6,3)最后访问根1。3. 递归实现最直观的“分治”思想递归是实现这三种遍历最符合直觉、代码也最简洁的方式。它完美体现了“分而治之”的思想要遍历整棵树我先访问根节点根据时机不同然后把遍历左子树和右子树的任务分别看作两个规模更小的、完全相同的遍历问题。下面是用Python定义的经典二叉树节点以及三种遍历的递归实现class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def preorder_recursive(root, result): 前序遍历递归 if not root: return result.append(root.val) # 访问根节点 preorder_recursive(root.left, result) # 遍历左子树 preorder_recursive(root.right, result) # 遍历右子树 def inorder_recursive(root, result): 中序遍历递归 if not root: return inorder_recursive(root.left, result) # 遍历左子树 result.append(root.val) # 访问根节点 inorder_recursive(root.right, result) # 遍历右子树 def postorder_recursive(root, result): 后序遍历递归 if not root: return postorder_recursive(root.left, result) # 遍历左子树 postorder_recursive(root.right, result) # 遍历右子树 result.append(root.val) # 访问根节点递归实现的要点与坑点递归终止条件if not root: return。这是最重要的没有它就会无限递归下去。它对应着走到了空节点意味着当前这条分支已经探索完毕。参数传递result列表作为一个“全局”记录者在递归过程中不断被修改。你也可以让递归函数直接返回一个列表但那样在拼接列表时会产生额外的空间开销。面试时两种写法都要会通常传递一个引用更高效。空间复杂度递归调用需要使用系统栈空间复杂度与树的高度成正比。在最坏情况树退化成一条链下空间复杂度是O(N)。这是递归方法的主要缺点。踩坑实录很多新手在写递归时容易在result.append(root.val)这一行犯错比如忘记append或者错误地return result.append(...)append方法返回None。记住递归函数的目的是“完成任务”遍历并收集而不是“返回结果”除非是自底向上的计算。另外一定要先判断root是否为空否则访问root.val会直接导致AttributeError。4. 迭代实现手动模拟栈理解递归的本质递归虽然简洁但有时我们需要更精细地控制遍历过程或者担心递归深度过深导致栈溢出。这时迭代法就派上用场了。迭代法的核心是用我们自己的栈Stack来模拟系统调用栈的过程。迭代法比递归难理解一些因为我们需要手动管理节点的访问和压栈顺序。三种遍历的迭代写法各有特点尤其是中序遍历与前序/后序有显著不同。4.1 前序遍历的迭代实现前序遍历是“根左右”迭代的思路很直接先把根节点压入栈。循环条件栈不为空。弹出栈顶节点并访问它这就是“根”。因为栈是“后进先出”为了保证接下来先处理左子树再处理右子树即“左右”的顺序我们需要先将右孩子压栈再将左孩子压栈。这样弹出时就会先弹出左孩子。def preorder_iterative(root): 前序遍历迭代 if not root: return [] stack, result [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 result4.2 中序遍历的迭代实现中序遍历是“左根右”不能像前序那样简单。我们需要用一个指针curr来模拟“一路向左到底”的过程同时用栈来保存“回退”的路径。从根节点开始当前节点curr不为空就将其压栈然后curr指向左孩子。这相当于深入左子树。当curr为空时说明已经走到最左下了。此时从栈中弹出节点这就是当前子树的“根”访问它。访问完后将curr指向该节点的右孩子开始处理右子树。重复上述过程。def inorder_iterative(root): 中序遍历迭代 stack, result, curr [], [], root while curr or stack: # 一路向左把节点压入栈 while curr: stack.append(curr) curr curr.left # 弹出栈顶节点并访问 curr stack.pop() result.append(curr.val) # 访问根节点 # 转向右子树 curr curr.right return result4.3 后序遍历的迭代实现后序遍历是“左右根”。我们可以利用前序遍历“根左右”的迭代版本稍作修改。前序是“根左右”如果我们改成“根右左”然后将结果反转不就得到“左右根”了吗这是一个非常巧妙的技巧。模仿前序遍历但调整左右子节点入栈顺序得到“根右左”的访问序列。将得到的序列反转。def postorder_iterative(root): 后序遍历迭代- 修改前序法 if not root: return [] stack, result [root], [] while stack: node stack.pop() result.append(node.val) # 访问“根” # 注意这里左孩子先入栈右孩子后入栈 # 以保证出栈顺序是“根 - 右 - 左” if node.left: stack.append(node.left) if node.right: stack.append(node.right) # 将“根右左”的结果反转得到“左右根” return result[::-1]迭代实现的要点与坑点前序最简单理解“右先左后”的压栈顺序是关键。中序最经典while curr or stack这个循环条件要记牢。内层的while curr负责向左深入外层的循环负责处理栈和右子树。后序取巧但有效理解其本质是对前序的变形和反转。面试时如果要求写非递归后序这种方法通常是可以接受的。当然也有更接近递归逻辑的双栈法但理解起来更复杂。空节点处理迭代法中对于空树的判断if not root依然重要。在中序遍历中curr初始化为root即使root为空while curr or stack也能正确处理。实操心得我强烈建议在理解递归的基础上亲手画图模拟一遍迭代法的执行过程。拿一张纸画一个简单的二叉树然后一步步模拟栈的变化和curr指针的移动。这个过程能极大地加深你对遍历顺序和栈这个数据结构作用的理解。面试时如果被问到“不用递归怎么做”你能清晰地画出这个过程比干巴巴地背代码要加分得多。5. 莫里斯遍历一种空间复杂度为O(1)的神奇方法无论是递归还是迭代我们都需要O(H)的额外空间H为树高。有没有可能只用常数空间呢有这就是莫里斯遍历Morris Traversal。它的核心思想是利用树中大量的空指针临时将当前节点的前驱节点中序遍历下的前一个节点的右孩子指向自己从而在遍历完左子树后能通过这个临时链接返回到根节点省去了栈的空间。莫里斯遍历主要应用于中序遍历它稍微修改后也能用于前序。后序的莫里斯遍历非常复杂一般不要求掌握。我们重点看中序。算法步骤中序莫里斯遍历初始化curr指向根节点。当curr不为空时 a. 如果curr没有左孩子则访问curr并将curr指向其右孩子。 b. 如果curr有左孩子 i. 找到curr在中序遍历下的前驱节点pre。即curr左子树中最右边的那个节点。 ii. 如果pre的右孩子为空将其右孩子设置为curr建立临时链接然后将curr指向其左孩子。 iii. 如果pre的右孩子已经是curr说明左子树已被遍历过则断开这个临时链接将pre.right置为None访问curr然后将curr指向其右孩子。def inorder_morris(root): 中序遍历莫里斯 - 空间O(1) result [] curr root while curr: if not curr.left: # 如果没有左孩子直接访问当前节点然后转向右孩子 result.append(curr.val) curr curr.right else: # 找到当前节点在中序遍历下的前驱节点 pre curr.left while pre.right and pre.right ! curr: pre pre.right if not pre.right: # 建立临时链接指向当前节点 pre.right curr curr curr.left else: # 临时链接已存在说明左子树已遍历完 pre.right None # 恢复树的结构 result.append(curr.val) curr curr.right return result莫里斯遍历的优缺点优点空间复杂度为O(1)对于内存严格受限的环境或巨型二叉树有优势。缺点修改了树的结构尽管是临时的。这在多线程环境或不允许修改原数据的场景下是致命的。同时代码逻辑比递归和迭代复杂容易出错。注意事项除非面试官明确要求或者问题有严格的O(1)空间限制否则在工程实践中优先使用递归或迭代法。莫里斯遍历更像一种炫技的算法用于展示对遍历过程的深刻理解。一定要在代码注释中写明它修改了树的结构。6. 层序遍历另一种维度的遍历方式虽然标题聚焦于前中后序但相关热词中频繁出现“层序遍历”它同样至关重要。层序遍历不属于深度优先搜索DFS的范畴而是**广度优先搜索BFS**在树上的应用。它按照树的层级从上到下、从左到右访问节点。实现层序遍历的核心数据结构是队列Queue。将根节点放入队列。当队列不为空时 a. 记录当前队列的长度level_size即当前层的节点数。 b. 循环level_size次每次从队列中取出一个节点访问并将其非空的左右子节点依次加入队列。 c. 当前层所有节点处理完毕结果中保存当前层的节点值列表然后继续下一层。from collections import deque def level_order_traversal(root): 层序遍历 if not root: return [] result [] queue deque([root]) while queue: level_size len(queue) current_level [] for _ in range(level_size): node queue.popleft() current_level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) return result对于之前的例子树层序遍历的结果是[[1], [2, 3], [4, 5, 6]]。层序遍历的妙用求二叉树的最大宽度在遍历每一层时记录该层的节点数取最大值。找到二叉树每层的最大值。判断是否是完全二叉树在层序遍历中如果遇到一个空节点之后又遇到了非空节点则不是完全二叉树。锯齿形Z字型层序遍历偶数层将结果反转即可。7. 遍历序列的威力重构二叉树与解决实际问题知道怎么遍历还不够更重要的是能利用遍历序列解决问题。一个经典面试题是已知两种遍历序列能否唯一确定一棵二叉树前序 中序可以唯一确定。原理前序序列的第一个元素一定是根节点。在中序序列中找到这个根节点其左边就是左子树的中序序列右边就是右子树的中序序列。根据左右子树的节点数量可以在前序序列中划分出左右子树的前序序列。递归进行即可。后序 中序可以唯一确定。原理后序序列的最后一个元素一定是根节点。后续步骤与前序中序类似。前序 后序一般不能唯一确定除非是满二叉树或真二叉树。因为无法区分左右子树的边界。重构二叉树的代码示例前序中序def build_tree(preorder, inorder): 根据前序和中序遍历序列构建二叉树 if not preorder or not inorder: return None # 前序第一个是根节点 root_val preorder[0] root TreeNode(root_val) # 在中序中找到根节点的位置 root_index_in_inorder inorder.index(root_val) # 划分左右子树的中序序列 left_inorder inorder[:root_index_in_inorder] right_inorder inorder[root_index_in_inorder 1:] # 划分左右子树的前序序列长度与中序子树相同 left_preorder preorder[1:1 len(left_inorder)] right_preorder preorder[1 len(left_inorder):] # 递归构建 root.left build_tree(left_preorder, left_inorder) root.right build_tree(right_preorder, right_inorder) return root避坑指南上面的代码为了清晰使用了list.index()和列表切片这在递归过程中会创建大量新列表空间效率不高。在面试或性能要求高的场景下应该使用索引指针来避免复制。即传递(pre_start, pre_end, in_start, in_end)这样的参数范围在原始数组上操作。8. 遍历的应用场景与高频面试题变形最后我们来聊聊遍历在实战和面试中的具体应用。死记硬背代码没用关键是理解每种遍历顺序带来的特性。前序遍历的应用复制一棵树先创建根节点再递归复制左右子树。这天然符合前序顺序。序列化二叉树如JSON化将树的结构转化为字符串或数组前序是一种很直观的方式。求从根到叶子的所有路径在深度优先遍历中前序顺序可以方便地在向下探索时记录路径。中序遍历的应用二叉搜索树BST的相关操作这是中序遍历的“主场”。BST的中序遍历结果是一个升序数组。利用这个特性可以验证一棵树是否是BST。在BST中查找第K小的元素。恢复一棵出错的BST两个节点被错误交换。表达式树求值对于表达式树运算符是根操作数是叶子中序遍历能得到中缀表达式可能需要加括号。后序遍历的应用释放二叉树内存必须先释放左右子树才能释放根节点。C/C中的free或delete操作。计算二叉树的高度/深度树的高度 1 max(左子树高度 右子树高度)。这需要先知道子树高度是典型的后序逻辑。判断一棵树是否是平衡二叉树在计算高度的同时判断平衡性。计算二叉树中任意两个节点的最近公共祖先LCA一种经典的递归解法就是后序遍历。路径总和问题判断是否存在从根到叶子节点路径和等于目标值虽然前序也能做但后序在回溯时撤销状态更清晰。层序遍历的应用寻找二叉树的最大/最小深度。寻找二叉树每层的最大值/平均值。二叉树的右视图/左视图即每一层最右边/最左边的节点。判断是否是完全二叉树。一道经典变形题迭代版后序遍历的另一种写法双栈法前面提到了修改前序反转的方法这里介绍更直观的双栈法它模拟了“左右根”的访问顺序更容易理解后序的本质。使用栈s1先将根节点压入。循环从s1弹出节点将其压入另一个栈s2。然后将该节点的左孩子、右孩子如果存在依次压入s1。重复步骤2-3直到s1为空。此时s2中节点的出栈顺序就是后序遍历顺序。def postorder_iterative_two_stack(root): 后序遍历迭代 - 双栈法 if not root: return [] s1, s2 [root], [] result [] while s1: node s1.pop() s2.append(node) if node.left: s1.append(node.left) if node.right: s1.append(node.right) while s2: result.append(s2.pop().val) return result这个方法的妙处在于s1的压栈顺序是“根 - 右 - 左”弹出压入s2后s2的压栈顺序是“左 - 右 - 根”最后从s2弹出时自然就是“左右根”。它虽然用了两个栈但逻辑非常清晰。遍历二叉树远不止前中后序这三种方式它们是理解树形结构操作的基石。从递归到迭代从栈到队列再到莫里斯遍历的奇技淫巧每一种实现都在加深我们对程序控制流和数据结构的理解。下次当你再看到遍历相关的题目时不妨先问自己这个问题需要以什么样的顺序访问节点是父节点优先前序是子节点优先后序还是需要按层级处理层序想清楚了这一点选择何种遍历方法以及采用递归还是迭代就都有了明确的依据。
