1. 二叉树遍历为什么每个程序员都得会如果你刚开始学数据结构或者正准备面试那“二叉树遍历”这个词你肯定不陌生。它就像学开车时的“挂挡”一样是基础中的基础但很多人其实只是背下了“先序、中序、后序”这几个名字真到用的时候脑子里还是一团浆糊。我见过不少朋友写递归遍历能写出来但一让解释非递归版本或者问一句“为什么中序遍历二叉搜索树能得到有序序列”就卡壳了。这其实挺危险的因为遍历不仅仅是“访问节点”那么简单它是你理解递归、栈、队列这些核心概念以及解决树形结构问题比如路径求和、最近公共祖先的基石。今天我们就用Python把二叉树遍历这件事彻底掰开揉碎了讲清楚。我们不只讲递归那“三板斧”更要深入非递归的迭代实现以及层次遍历这种广度优先的玩法。我会带你从最基本的节点定义开始一步步实现所有遍历方法并解释清楚每一步背后的“为什么”。比如为什么非递归的先序遍历要用栈为什么层次遍历天然适合用队列递归的调用栈和显式使用的栈本质上是不是一回事搞懂这些你才算真正掌握了遍历。这篇文章适合所有阶段的Python开发者。如果你是新手可以跟着代码一步步敲理解树的结构如果你有基础可以直接跳到非递归和层次遍历部分看看有没有你之前忽略的细节。我会尽量用最直白的语言和类比让你不仅“会写”更能“懂原理”。毕竟在编程里知其然更要知其所以然。2. 构建基石定义二叉树节点与创建测试树在开始遍历之前我们得先有棵树。在Python里定义一棵二叉树最经典的方式就是用一个类来表示节点。这个类非常简单但它是所有后续操作的基础。2.1 节点类的定义一个二叉树节点通常包含三个部分节点存储的值val指向左子节点的引用left以及指向右子节点的引用right。初始化时左子节点和右子节点默认为None表示这是一个叶子节点或者尚未连接子节点。class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right这个定义看似简单但有几个关键点需要注意self.val val这里存储节点的核心数据。它可以是整数、字符串甚至是另一个复杂对象这取决于你的应用场景。在算法题中最常见的是整数值。self.left和self.right这是两个“指针”在Python中是引用它们将节点连接起来形成树结构。None在这里扮演着空指针的角色标志着一条分支的结束。为什么用类使用类来封装节点数据和行为是面向对象思想的体现。它清晰地将数据val和结构关系left,right绑定在一起使得代码更易读、易维护。你也可以用字典如{val: 1, left: None, right: None}来实现但类的形式在访问属性和方法扩展上更具优势。2.2 手动创建一棵测试树为了演示各种遍历我们需要一棵具体的树。假设我们要创建下面这棵二叉树1 / \ 2 3 / \ \ 4 5 6对应的节点关系是节点1是根节点其左孩子是2右孩子是3节点2的左孩子是4右孩子是5节点3的右孩子是6左孩子为空。用代码创建这棵树的过程就是从叶子节点开始自底向上地构建引用关系# 创建叶子节点 node4 TreeNode(4) node5 TreeNode(5) node6 TreeNode(6) # 创建中间节点并连接其子节点 node2 TreeNode(2, leftnode4, rightnode5) # 节点2的左孩子是4右孩子是5 node3 TreeNode(3, rightnode6) # 节点3的右孩子是6左孩子默认为None # 创建根节点并连接左右子树 root TreeNode(1, leftnode2, rightnode3) # 根节点1的左孩子是2右孩子是3现在变量root就指向了这棵树的根节点。通过root.left可以访问节点2root.left.left可以访问节点4。这种手动创建方式在理解概念和调试小规模代码时非常直观。注意在更实际的场景中比如从LeetCode做题或者处理序列化数据如列表[1,2,3,4,5,None,6]我们通常会写一个专门的建树函数。但作为入门手动构建能让你最清晰地看到内存中引用关系是如何建立的这是理解后续递归和迭代遍历的关键。如果你对引用传递不理解很容易在修改节点时出错。记住node2.left node4意味着node2的left属性现在和变量node4指向了同一个TreeNode对象。有了这棵具体的树我们就可以开始探索各种遍历方法并观察它们访问节点的顺序有何不同。遍历的本质就是制定一套规则来决定我们以何种顺序“访问”比如打印、存储树中的每一个节点。3. 深度优先遍历DFS递归的优雅与迭代的掌控深度优先遍历DFS顾名思义就是尽可能深地搜索树的分支。当一条路走到头遇到叶子节点时再回溯到上一个分叉点探索另一条路。递归实现DFS非常直观因为它完美契合了“树”这种自相似子树也是树的数据结构。但理解其非递归的迭代版本能让你对程序运行时的栈空间有更深刻的认识。3.1 递归遍历理解“序”的核心递归遍历的代码极其简洁其核心区别仅在于“访问根节点”这个操作在递归调用中的执行时机。我们定义一个traverse函数它接收一个树节点作为参数。先序遍历Preorder Traversal规则访问根节点 - 递归遍历左子树 - 递归遍历右子树。def preorder_recursive(root): result [] def traverse(node): if not node: # 递归终止条件当前节点为空 return result.append(node.val) # 访问根节点 traverse(node.left) # 遍历左子树 traverse(node.right) # 遍历右子树 traverse(root) return result对于我们的测试树调用preorder_recursive(root)会返回[1, 2, 4, 5, 3, 6]。你可以想象成从根节点开始第一次遇到一个节点就立刻“办事”访问然后再去处理它的左右孩子。中序遍历Inorder Traversal规则递归遍历左子树 - 访问根节点 - 递归遍历右子树。def inorder_recursive(root): result [] def traverse(node): if not node: return traverse(node.left) # 遍历左子树 result.append(node.val) # 访问根节点 traverse(node.right) # 遍历右子树 traverse(root) return result调用inorder_recursive(root)返回[4, 2, 5, 1, 3, 6]。这是二叉搜索树BST的灵魂所在因为BST的定义是左子树所有节点值 根节点值 右子树所有节点值所以中序遍历BST必然得到一个升序序列。这个特性被广泛用于BST的验证、查找和第K小元素等问题。后序遍历Postorder Traversal规则递归遍历左子树 - 递归遍历右子树 - 访问根节点。def postorder_recursive(root): result [] def traverse(node): if not node: return traverse(node.left) # 遍历左子树 traverse(node.right) # 遍历右子树 result.append(node.val) # 访问根节点 traverse(root) return result调用postorder_recursive(root)返回[4, 5, 2, 6, 3, 1]。后序遍历的特点是当你访问一个节点时它的所有子孙节点都已经被访问过了。这个特性在“释放树的内存”或“计算子树的结果如子树和”等场景中非常有用因为你需要先得到子节点的结果才能计算当前节点的结果。递归的心得与陷阱递归代码简洁但理解其执行流是关键。你可以画一个简单的树然后像CPU一样一步步模拟函数调用栈。另外递归有深度限制对于极端倾斜的树退化成一个链表可能会引发“递归深度超过最大限制”的错误。这就是为什么我们必须要掌握非递归方法。3.2 非递归遍历显式使用栈模拟过程非递归遍历的核心思想就是用我们自定义的栈stack来模拟递归函数调用时的系统栈。我们需要手动管理节点的访问和压栈、出栈顺序。非递归先序遍历先序遍历的非递归实现是最直观的。思路是将根节点压入栈。循环当栈不为空时 a. 弹出栈顶节点并访问它。 b.先将右子节点压栈再将左子节点压栈注意顺序。 为什么是先右后左因为栈是“后进先出”LIFO的。我们希望左子节点先被访问所以它必须后入栈这样它就会先出栈。def preorder_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非递归中序遍历中序遍历的非递归实现稍复杂是面试常考点。思路是用一个指针cur从根节点开始。循环当cur不为空或栈不为空时 a. 一直向左走把沿途所有节点压入栈while cur: stack.append(cur); cur cur.left。这模拟了递归中“遍历左子树”的过程。 b. 弹出栈顶节点这是当前能访问的最左节点访问它。 c. 将cur指向弹出节点的右子节点开始处理右子树。def inorder_iterative(root): result [] stack [] cur root while cur or stack: # 模拟递归压栈走到最左边 while cur: stack.append(cur) cur cur.left # 弹出并访问节点 node stack.pop() result.append(node.val) # 转向右子树 cur node.right return result这个算法巧妙地用栈记录了回去的路径。cur指针负责探索新的左分支而栈负责在走到头时回溯到上一个分叉点。非递归后序遍历后序遍历的非递归实现有多种方法其中一种易于理解的是利用先序遍历的变形。我们知道先序是“根-左-右”而后序是“左-右-根”。如果我们能实现“根-右-左”的遍历再把结果反转不就得到“左-右-根”了吗def postorder_iterative(root): if not root: return [] result [] stack [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] # 反转结果得到后序这种方法非常取巧代码和先序遍历几乎一样只是入栈顺序和最后一步反转的区别。另一种更正统的方法是记录上一个访问的节点来判断当前节点的右子树是否已被访问逻辑稍复杂但空间效率一致。迭代实现的实战技巧在写非递归遍历时我最喜欢在白板或纸上画一个小树然后一步步模拟栈和指针cur的变化。对于中序遍历关键是理解内层while循环“一撸到底”压左节点的过程。对于后序遍历如果你怕忘记反转可以在代码里显式写上注释# 技巧修改自先序最后反转。在面试中解释清楚“为什么用栈”以及“入栈出栈顺序如何决定访问顺序”比死记硬背代码更有价值。4. 广度优先遍历BFS层次遍历与队列的应用深度优先遍历是一条路走到黑而广度优先遍历BFS则是“雨露均沾”按距离根节点的深度一层一层地访问。对于二叉树来说BFS就是层次遍历Level Order Traversal。4.1 基础层次遍历层次遍历天然适合使用队列Queue这种“先进先出”FIFO的数据结构。算法步骤非常清晰将根节点放入队列。循环当队列不为空时 a. 弹出队列前端的节点并访问。 b. 将该节点的左子节点如果存在加入队列。 c. 将该节点的右子节点如果存在加入队列。from collections import deque def level_order(root): if not root: return [] result [] queue deque([root]) # 使用deque双端队列popleft()效率高 while queue: node queue.popleft() # 弹出队首节点 result.append(node.val) # 访问 # 将子节点加入队尾 if node.left: queue.append(node.left) if node.right: queue.append(node.right) return result对于我们的测试树level_order(root)返回[1, 2, 3, 4, 5, 6]。可以看到节点严格按照从上到下、从左到右的顺序被访问。为什么用队列而不用栈这是理解BFS/DFS区别的关键。在层次遍历中我们希望先被发现的节点先被访问。节点1第一层先入队也先出队它出队时把它的孩子节点2和3第二层加入队尾。这样在节点1被访问后队列里是[2, 3]节点2会先于节点3被访问保证了“从左到右”的顺序。如果使用栈就会变成深度优先顺序就乱了。4.2 按层分组输出很多时候我们不仅需要所有节点的值还需要知道哪些节点属于同一层。例如LeetCode上经典的“二叉树的层次遍历 II”或“锯齿形层次遍历”问题。实现的关键在于在每一轮循环开始时我们都能知道当前队列的长度这个长度就是当前层的节点数。def level_order_grouped(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调用level_order_grouped(root)会返回[[1], [2, 3], [4, 5, 6]]。这个for _ in range(level_size):的循环是算法的精髓。它确保了在一次外层while循环中我们只处理当前层的节点并在处理过程中将下一层的节点加入队列为下一次循环做好准备。4.3 层次遍历的变体与应用掌握了分层遍历的模板很多变体问题就迎刃而解自底向上层次遍历只需将result.append(current_level)改为result.insert(0, current_level)或者在最后返回result[::-1]。锯齿形Zigzag层次遍历增加一个布尔标志left_to_right在每一层开始时根据其值决定是将current_level直接加入结果还是反转后再加入current_level[::-1]并在每层处理后翻转这个标志。寻找每层的最大值/平均值在for循环中不再存储所有值而是计算最大值、总和等。二叉树的最小深度使用BFS当遇到第一个叶子节点node.left is None and node.right is None时当前的层数就是最小深度。这比DFS要高效因为DFS必须遍历所有节点才能确定最小深度。层次遍历的踩坑点最常见的错误是在分层遍历时没有使用level_size固定循环次数而是直接while queue并在循环内popleft。这样会导致不同层的节点混在一起因为你在处理当前层节点的同时队列里也在不断加入下一层的节点。另一个坑是对于空树root is None的情况一定要在开头判断并返回否则deque([None])会导致后续逻辑错误。在工程代码中层次遍历常用于需要按层级处理数据的场景比如社交网络中的好友关系扩散、多级目录的渲染等。5. 遍历算法的综合对比与实战选择到现在为止我们已经实现了二叉树的所有主要遍历方法。是时候把它们放在一起从时间、空间复杂度以及适用场景上做个全面对比这样你在实际编程中才能做出最合适的选择。5.1 时间复杂度与空间复杂度分析所有遍历方法无论是递归还是迭代DFS还是BFS时间复杂度都是 O(N)其中 N 是树中的节点数。因为你必须访问每个节点一次不可能比这更少。空间复杂度才是区分它们的关键递归DFS空间复杂度取决于递归调用栈的最大深度也就是树的高度 H。在平衡二叉树中H ≈ log₂N空间复杂度为 O(logN)。在最坏情况树退化成链表下H N空间复杂度为 O(N)。迭代DFS使用栈空间复杂度同样为 O(H)因为栈中最多同时存储一条路径上的节点。平衡树时为 O(logN)退化树时为 O(N)。迭代BFS使用队列空间复杂度取决于队列中同时存在的最大节点数这发生在树的宽度最大的一层。对于一棵完全二叉树最宽的一层大约有 N/2 个节点因此空间复杂度为 O(N)。在平衡树中这也是 O(N) 级别因为最后一层的节点数最多。遍历方式实现方法时间复杂度空间复杂度平均/最坏核心数据结构先序、中序、后序递归O(N)O(H) / O(N)系统调用栈先序、中序、后序迭代O(N)O(H) / O(N)显式栈Stack层次遍历迭代O(N)O(W) / O(N)队列QueueH: 树的高度 W: 树的最大宽度 N: 节点总数5.2 如何根据场景选择遍历方法选择哪种遍历从来不是看哪种代码更短而是看你的目的是什么。1. 当你需要按特定顺序处理或输出节点值时需要序列化二叉树并希望易于重建先序遍历是常见选择。因为序列的第一个元素就是根节点便于递归反序列化。处理二叉搜索树BST中序遍历是唯一选择。它能得到有序序列用于验证BST、查找第K小的元素、恢复错误的BST等。后序遍历常用于需要先处理子节点再处理父节点的场景。比如计算二叉树中每个节点的子树和。删除二叉树需要先删除子节点再释放父节点内存。判断一棵树是否平衡需要先知道左右子树的高度。2. 当你需要按层级处理节点时任何需要按层分析或寻找最短路径的问题都应用层次遍历BFS。例如找出二叉树每层的最大值或平均值。寻找从根节点到叶子节点的最短路径最小深度。在树中寻找距离某个节点最近的特定值节点。3. 当树的形状特殊时考虑空间复杂度如果树非常高且瘦接近链表避免使用递归和基于栈的DFS因为递归深度可能导致栈溢出。此时迭代BFS可能是更安全的选择尽管它可能占用更多宽度空间但在退化树中宽度为1。如果树非常平衡且宽递归DFSO(logN)空间通常比BFSO(N)空间更节省内存。4. 关于递归与迭代的选择递归代码简洁逻辑清晰易于理解和证明正确性。是表达树形结构算法的自然方式。优先考虑使用递归除非有明确的限制。迭代能完全避免递归深度限制并且有时可以通过调整栈/队列的操作顺序来实现更复杂的遍历如Morris遍历能在O(1)额外空间下完成中序遍历。当问题明确要求不使用递归或者树的深度可能极大时必须使用迭代。我的实战经验在平时刷题或开发中我遵循一个简单的决策流1) 先判断问题本质是否需要层次信息是 - BFS。2) 如果不是优先用递归实现DFS因为写起来快不易错。3) 只有在明确担心栈溢出如处理超深JSON、某些特化场景或者面试官要求展示迭代写法时我才手动写栈或队列的版本。对于中序遍历我强烈建议掌握迭代写法因为它是理解栈如何模拟递归的绝佳例子面试频率极高。记住没有“最好”的遍历只有“最合适”的遍历。6. 遍历算法的扩展与高级话题掌握了基础遍历我们就可以解决LeetCode上大部分树相关问题了。但遍历的玩法远不止于此一些高级技巧和变体能让你在解决复杂问题时更加游刃有余。6.1 Morris遍历极致的空间优化无论是递归还是迭代我们都需要O(H)的额外空间栈或队列。有没有可能只用O(1)的额外空间完成遍历呢有这就是Morris遍历。它的核心思想是利用树中大量的空指针None来临时存储回溯到上层节点的路径信息。以Morris中序遍历为例其算法步骤如下初始化当前节点cur为根节点。当cur不为空时循环 a. 如果cur没有左孩子则访问cur并将cur指向其右孩子cur cur.right。 b. 如果cur有左孩子 i. 找到cur左子树上的最右节点记为predecessor中序遍历下cur的前驱节点。 ii. 如果predecessor的右孩子为空将其右孩子指向cur建立临时链接然后将cur指向其左孩子cur cur.left。 iii. 如果predecessor的右孩子已经是cur说明左子树已遍历完则断开这个临时链接predecessor.right None访问cur然后将cur指向其右孩子cur cur.right。def inorder_morris(root): result [] cur root while cur: if not cur.left: # 如果没有左孩子访问当前节点并转向右子树 result.append(cur.val) cur cur.right else: # 找到左子树的最右节点前驱 predecessor cur.left while predecessor.right and predecessor.right ! cur: predecessor predecessor.right if not predecessor.right: # 建立临时链接指向cur然后深入左子树 predecessor.right cur cur cur.left else: # 临时链接已存在说明左子树已遍历完 predecessor.right None # 断开链接 result.append(cur.val) # 访问当前节点 cur cur.right # 转向右子树 return resultMorris遍历的妙处在于它通过修改叶子节点的右指针之后会恢复实现了不用栈的回溯。整个过程中除了几个指针变量没有使用任何额外数据结构空间复杂度为O(1)。当然它修改了树的结构尽管是临时的这在某些只读场景下不可用并且代码逻辑比递归复杂得多。通常只在有严格空间限制如嵌入式环境的场合才会使用。6.2 遍历序列的应用重构二叉树一个经典的问题是给定两种遍历序列如先序和中序能否唯一地重构出原来的二叉树答案是肯定的。原理在先序遍历中第一个元素一定是根节点。在中序遍历中根节点将序列分成了左子树的中序序列和右子树的中序序列。通过这个信息我们可以在先序序列中找到左右子树的先序序列从而递归地构建整棵树。def build_tree(preorder, inorder): 根据先序和中序遍历序列构建二叉树 :type preorder: List[int] :type inorder: List[int] :rtype: TreeNode if not preorder or not inorder: return None # 先序序列的第一个值是根节点 root_val preorder[0] root TreeNode(root_val) # 在中序序列中找到根节点的位置 root_index_in_inorder inorder.index(root_val) # 递归构建左子树和右子树 # 左子树的先序序列preorder[1 : 1root_index_in_inorder] # 左子树的中序序列inorder[:root_index_in_inorder] root.left build_tree(preorder[1:1root_index_in_inorder], inorder[:root_index_in_inorder]) # 右子树的先序序列preorder[1root_index_in_inorder:] # 右子树的中序序列inorder[root_index_in_inorder1:] root.right build_tree(preorder[1root_index_in_inorder:], inorder[root_index_in_inorder1:]) return root类似地通过中序后序也可以唯一确定一棵二叉树后序的最后一个元素是根。但是先序后序不能唯一确定一棵二叉树除非这是一棵满二叉树。这是一个重要的考点。6.3 在遍历中附加操作解决实际问题单纯的遍历输出节点值意义不大遍历的强大之处在于我们可以在访问节点的同时进行各种计算和判断从而解决复杂问题。例子1寻找二叉树的最大深度递归DFSdef max_depth(root): if not root: return 0 left_depth max_depth(root.left) # 遍历左子树得到其深度 right_depth max_depth(root.right) # 遍历右子树得到其深度 return max(left_depth, right_depth) 1 # 访问根节点深度为左右子树最大深度1这本质上是一个后序遍历因为我们需要先知道左右子树的深度才能算出当前节点的深度。例子2判断二叉树是否对称递归DFSdef is_symmetric(root): def check(left, right): if not left and not right: return True if not left or not right: return False if left.val ! right.val: return False # 关键递归检查左子的左子树和右子的右子树以及左子的右子树和右子的左子树 return check(left.left, right.right) and check(left.right, right.left) return check(root, root) if root else True这里我们同时遍历两棵树根节点的左右子树是一种特殊的“同步遍历”。例子3求二叉树的直径后序遍历的变体直径是任意两个节点间最长路径的长度。这条路径可能不经过根节点。思路是对于每个节点计算其左右子树的最大深度之和经过该节点的最长路径长度并在递归过程中更新全局最大值。def diameter_of_binary_tree(root): self.diameter 0 def depth(node): if not node: return 0 left_depth depth(node.left) right_depth depth(node.right) # 更新直径经过当前节点的最长路径长度 self.diameter max(self.diameter, left_depth right_depth) # 返回以当前节点为根的子树的最大深度 return max(left_depth, right_depth) 1 depth(root) return self.diameter高级技巧的心得Morris遍历虽然炫技但除非面试官明确要求或空间极端受限否则在工程中我几乎从不使用因为可读性太差容易出错。而利用遍历序列重建二叉树是理解二叉树结构的绝佳练习务必掌握。最重要的是要养成在遍历框架中思考问题的习惯。看到树的问题先想这个问题需要在什么时机访问节点前、中、后获取什么信息这往往能帮你迅速定位到该用哪种遍历的变体。比如求路径和通常用先序遍历在访问节点时累加而像“二叉树的最近公共祖先”这种问题则需要后序遍历利用左右子树的返回值来判断。