1. 从“遍历”说起为什么我们需要系统地访问一棵树在编程和数据结构的世界里“遍历”这个词听起来有点学术但它的本质很简单就是按照某种规则把数据结构里的每个元素都“访问”一遍一个也不落下。想象一下你刚搬进一个新家家里堆满了还没拆封的纸箱。为了找到你的咖啡杯你可能需要打开每一个箱子看看。这个“打开每一个箱子看看”的过程就是一种遍历——只不过你遍历的对象是“纸箱集合”。那么当这个“集合”不是平铺直叙的一排箱子而是一棵有着复杂枝杈的“树”时事情就变得有趣了。树结构无处不在你电脑里的文件系统是树文件夹套文件夹公司的组织架构图是树CEO下面有各个部门总监总监下面有经理甚至一个家族的家谱也是树。在这些场景下“遍历”意味着你需要一种系统性的方法来访问树中的每一个节点比如每一个文件、每一位员工、每一位家族成员并且确保不会漏掉谁也不会重复访问谁。为什么这如此重要因为访问是操作的前提。你想统计一个文件夹下所有文件的总大小遍历文件树你想计算公司所有员工的薪资总和遍历组织树或者你想在家谱里找到所有“王”姓的成员遍历家谱树。在这些操作执行之前你必须先“见到”每一个节点。遍历就是为你提供见到它们的地图和方法。不同的遍历顺序就像不同的参观路线有的路线让你先看主干再看枝叶深度优先有的路线让你一层一层地看广度优先对于二叉树这种特殊结构根据访问“根节点”的时机不同又衍生出先序、中序、后序这三种经典路线。选择哪种路线取决于你想干什么。理解这些遍历就是拿到了操作树形数据的万能钥匙。2. 两种根本策略深度优先DFS与广度优先BFS面对一棵树我们有两种最根本的探索策略它们的思想截然不同也直接决定了后续所有具体遍历方法的基础。2.1 深度优先搜索DFS一条道走到黑再回头DFS的策略非常像我们走迷宫或者探索一个洞穴系统选择一条路径尽可能深地走下去直到走到尽头叶子节点然后退回上一个岔路口选择另一条未曾走过的路继续深入。核心思想与递归实现DFS天然适合用递归来实现因为它的过程就是不断地“自我重复”。对于树中的一个节点DFS的访问逻辑可以概括为访问当前节点。对于当前节点的每一个子节点在二叉树里是左孩子和右孩子将其作为新的“当前节点”重复步骤1。用伪代码表示一个通用的树多叉树的DFS递归函数大概是这个样子def dfs(node): if node is None: # 递归的终止条件到达空节点 return # 1. 在这里“访问”节点比如打印节点值 visit(node) # 2. 递归地访问所有子节点 for child in node.children: dfs(child)这种“递归”实现非常简洁它隐式地使用了一个叫做“调用栈”的东西来记录我们的回溯路径。当我们深入调用dfs(child)时当前函数的状态执行到了哪个子节点被压入栈当递归返回时我们从栈顶弹出状态回到上一个岔路口。迭代实现与显式栈不是所有编程环境都鼓励深度递归比如递归层数过深可能导致栈溢出。我们可以用循环和一个显式的“栈”Stack数据结构来模拟递归过程实现迭代版的DFS。迭代版DFS的步骤是将根节点压入栈。当栈不为空时 a. 弹出栈顶节点并访问它。 b.将这个节点的所有子节点按照逆序压入栈中。为什么逆序因为栈是“后进先出”为了保证访问顺序符合我们的预期比如希望先处理左边的子节点就需要后压入左节点。def dfs_iterative(root): if not root: return stack [root] # 显式栈 while stack: node stack.pop() # 弹出栈顶 visit(node) # 将子节点逆序压栈以保证正序访问 for child in reversed(node.children): stack.append(child)DFS的特点与应用场景特点优先探索纵向深度适合寻找是否存在某条路径、检查某个属性是否在深处成立。典型应用路径查找比如在文件树中查找一个深藏在多层文件夹下的特定文件。拓扑排序在有向无环图DAG中安排任务顺序。解决回溯问题如八皇后、数独在做出一个选择深入一层后如果发现不行就退回回溯。遍历DOM树网页解析时深度优先的方式很常见。注意递归DFS代码简洁但需要注意递归深度限制。对于非常深的树迭代DFS是更安全的选择。另外如果树结构中有环在图结构中常见DFS需要记录已访问节点通常用一个visited集合否则会陷入无限循环这在纯粹的树结构中不会发生因为树是无环的。2.2 广度优先搜索BFS层层递进稳扎稳打BFS的策略则像水波纹扩散或者像组织一场会议你先邀请第一层的人根节点等他们都到了再让他们各自邀请自己的直接下属子节点来第二批人齐了再让第二批人邀请他们的下属如此类推。核心思想与队列实现BFS无法用简单的递归优雅描述它必须使用一个“队列”Queue作为核心数据结构。将根节点放入队列。当队列不为空时 a. 从队列头部取出一个节点并访问。 b. 将这个节点的所有子节点依次放入队列尾部。from collections import deque def bfs(root): if not root: return queue deque([root]) # 使用双端队列从左边弹出效率高 while queue: level_size len(queue) # 当前层的节点数 for _ in range(level_size): # 一次性处理完同一层的所有节点 node queue.popleft() # 从队头取出 visit(node) # 将子节点按顺序加入队尾 for child in node.children: queue.append(child) # 可选在这里可以知道一层结束了方便进行按层操作上面代码中我特意加入了level_size和内部的for循环这让我们可以清晰地知道当前正在访问哪一层这是BFS一个非常强大的特性——按层遍历。BFS的特点与应用场景特点优先探索横向广度总是先访问离起点最近的节点。典型应用最短路径在无权图或树中BFS找到的路径就是边数最少的路径。比如在社交网络中寻找你和另一个人的最少介绍人链路。按层处理比如打印树的层级结构、计算树的层高深度、寻找每层的最大值等。广播消息在网络中消息需要以最小的跳数传播到所有节点。迷宫最短路径在网格迷宫中BFS可以找到从起点到终点的最短步数。注意BFS的空间复杂度通常比DFS高因为在最坏情况下一棵完全二叉树队列中需要存储最后一层的所有节点数量约为O(N)。而DFS在最坏情况下一条链的空间复杂度也是O(N)但在平衡树中DFS的空间复杂度是O(log N)。因此在树非常宽或者你需要最短路径特性时用BFS在树很深但不太宽或者需要探索所有可能路径时DFS更合适。3. 二叉树的经典序先序、中序、后序二叉树是树家族中最常用、最特化的一种结构每个节点最多有两个子节点左孩子和右孩子。针对二叉树的节点访问顺序根据“根节点”(D)、“左子树”(L)、“右子树”(R)这三者访问的先后排列诞生了三种经典的深度优先遍历次序它们都是DFS思想的具体体现。3.1 先序遍历Pre-order, DLR顺序根节点 - 左子树 - 右子树。操作一到某个节点先“办正事”访问然后再去处理它的左右孩子。递归实现def preorder(node): if node is None: return visit(node) # 1. 访问根 preorder(node.left) # 2. 遍历左子树 preorder(node.right) # 3. 遍历右子树迭代实现使用栈def preorder_iterative(root): if not root: return stack [root] while stack: node stack.pop() visit(node) # 栈是后进先出所以先压右孩子再压左孩子 if node.right: stack.append(node.right) if node.left: stack.append(node.left)应用场景先序遍历会首先访问根节点这非常适用于“复制一棵树”或“序列化一棵树”将树结构转化为字符串或数组存储。因为你拿到根节点后可以立刻开始重建过程。在表达式树中先序遍历产生的是前缀表达式波兰表达式。3.2 中序遍历In-order, LDR顺序左子树 - 根节点 - 右子树。操作对于一个节点先“深入探索”它的整个左翼然后回来访问它自己最后再去探索它的右翼。递归实现def inorder(node): if node is None: return inorder(node.left) # 1. 遍历左子树 visit(node) # 2. 访问根 inorder(node.right) # 3. 遍历右子树迭代实现这是三种遍历中迭代实现稍复杂的一个def inorder_iterative(root): stack [] curr root while curr or stack: # 一路向左把经过的节点都压入栈 while curr: stack.append(curr) curr curr.left # 弹出栈顶节点这是最左边的节点 curr stack.pop() visit(curr) # 访问它 # 转向右子树 curr curr.right这个迭代算法的关键在于理解栈里保存的不是待访问的节点而是已经路过但尚未访问的“根”节点。我们沿着左孩子指针一路下探把途径的节点压栈直到左边走到头curr为None。然后从栈中弹出一个节点访问此时它是它自己子树的“根”接着去处理它的右子树。应用场景这是最重要的遍历方式之一。对于二叉搜索树BST中序遍历会得到一个升序或降序序列这是BST的核心性质。因此任何需要按顺序输出BST节点值的操作都离不开中序遍历。它也常用于表达式树中序遍历会产生中缀表达式就是我们平常写的表达式但需要加括号来消除歧义。3.3 后序遍历Post-order, LRD顺序左子树 - 右子树 - 根节点。操作对于一个节点先把它的“身后事”左右子树都处理干净最后再来处理它自己。递归实现def postorder(node): if node is None: return postorder(node.left) # 1. 遍历左子树 postorder(node.right) # 2. 遍历右子树 visit(node) # 3. 访问根迭代实现有多种方法这里介绍一种利用“反转”技巧的易懂方法def postorder_iterative(root): if not root: return stack [root] result_stack [] # 辅助栈用于反转顺序 while stack: node stack.pop() result_stack.append(node) # 将节点放入结果栈 # 注意压栈顺序先左后右 if node.left: stack.append(node.left) if node.right: stack.append(node.right) # 此时result_stack中是 根-右-左弹出顺序就是左-右-根 while result_stack: visit(result_stack.pop())更经典的迭代实现需要记录上一个访问的节点来判断状态但上述方法利用“先序遍历的变种根-右-左 反转”来得到后序非常巧妙且易于记忆。应用场景后序遍历常用于“先子后父”的场景。比如计算一个目录树的总大小你必须先知道所有子目录和文件的大小才能汇总出当前目录的大小。删除一棵树也需要后序你必须先安全地删除所有子节点才能删除父节点否则会出现悬空指针。在表达式树中后序遍历产生的是后缀表达式逆波兰表达式这种表达式特别方便计算机用栈来求值。实操心得记忆这三种顺序有个小窍门。“先”、“中”、“后”指的是根节点被访问的时机。在递归代码中visit(node)这行代码放在哪里就是什么遍历。放在最前面是先序放在中间是中序放在最后是后序。理解了这个递归写法就永远不会记错。4. 遍历的实战理解、调试与常见问题理解了原理和代码我们还需要在实战中运用和调试。遍历是许多复杂树操作的基础这里分享一些关键的实战经验和常见“坑点”。4.1 可视化跟踪理解遍历过程的利器对于初学者最大的困惑是“递归到底是怎么跑的”。一个极其有效的方法是画图和手动模拟栈。画出一棵简单的二叉树节点标上字母或数字。拿一张纸作为“调用栈”。逐步执行递归函数进入一个函数访问一个节点就把这个函数调用包含当前节点和程序执行位置压入你的纸栈。执行到递归调用时比如preorder(node.left)暂停当前函数将新的调用压栈。当遇到node is None递归出口时从栈顶弹出这个调用回到上一层调用暂停的位置继续执行。在visit的地方在节点上做个标记。通过几次这样的手动模拟你会对递归的“深入、返回、再深入”有刻骨的理解。对于迭代法同样可以手动模拟栈或队列的变化。4.2 遍历中的“访问”操作不止是打印我们一直用visit(node)这个抽象操作。在实际应用中“访问”可以是任何事修改节点值比如给树中每个节点的值加1。收集节点将节点值存入一个列表最终返回这个列表。这就是序列化。判断条件检查树是否对称、计算树的高度、寻找最大值等。构建数据结构在遍历过程中利用得到的信息构建另一棵树或一个链表。例如通过中序遍历将二叉搜索树转换为有序双向链表就是一个经典的遍历应用。在inorder遍历中当visit(node)时我们不是打印而是修改当前节点和前驱节点的指针将它们连接起来。4.3 常见问题与避坑指南空指针异常这是最常见的错误。在递归中if node is None: return这个终止条件至关重要。在迭代法中向栈或队列添加子节点前必须判断子节点是否为空。# 错误示范迭代DFS中 stack.append(node.left) # 如果node.left是None后续pop出来访问会出错 # 正确示范 if node.left: stack.append(node.left)修改结构的同时遍历这是一个危险操作。比如你想在遍历一棵树的同时删除所有值为偶数的节点。如果你在DFS递归中访问到一个节点后直接将其从父节点断开那么后续递归调用dfs(node.left)可能会访问到一个已经不属于这棵树的节点或者导致指针错乱。安全的做法通常是后序遍历先递归处理好左右子树返回时再决定如何处理当前根节点。或者先进行一次遍历收集需要删除的节点再进行一次遍历执行删除。迭代遍历的栈/队列状态混淆写迭代BFS时误用了栈导致变成了DFS写迭代DFS时子节点压栈顺序错了导致访问顺序不符合预期。记住口诀BFS用队列FIFODFS用栈LIFO。对于二叉树先序迭代压栈顺序是先右后左。二叉树与多叉树的遍历代码混淆二叉树的遍历代码通常明确写node.left和node.right。而多叉树的遍历需要循环处理node.children列表。在写通用树库时要注意抽象。忽略遍历的应用场景导致性能问题比如要判断一棵树是否平衡左右子树高度差不超过1用后序遍历可以在每个节点处收集子树高度并判断时间复杂度O(N)。如果错误地用先序遍历在每个节点处都去计算一次子树高度计算高度本身又是O(N)的遍历会导致O(N²)的复杂度。选择合适的遍历顺序常常是写出高效算法的关键。5. 从遍历到更高阶的树操作遍历是基石掌握了它你就可以解决树领域的绝大多数问题。很多面试题和实际算法都是遍历的变种或组合。组合遍历有些问题需要结合多种遍历。例如“根据二叉树的中序遍历和后序遍历序列重建二叉树”。解决思路是后序序列的最后一个元素是根节点用这个根节点去中序序列中找到左右子树的分界点从而确定左右子树的范围然后递归地在对应的子序列中重复这个过程。这里就用到了后序确定根和中序划分左右的信息。带状态的遍历在遍历过程中我们可能需要携带一些额外信息。例如求根节点到叶子节点的所有路径。我们可以在DFS递归时额外传递一个path列表参数记录从根到当前节点的路径。当到达叶子节点时就将path的副本保存下来。这个path就是遍历的“状态”。Morris遍历这是一种神奇的、空间复杂度为O(1)的二叉树遍历算法。它通过利用树中大量的空指针叶子节点的left/right为None来临时存储信息实现遍历。它非常巧妙但理解和实现难度较高是遍历算法的一个进阶知识点。其核心思想是在遍历过程中临时修改树的结构最后会恢复为当前节点找到它的中序前驱节点并建立链接从而在访问完左子树后能顺利返回到根节点。遍历这个看似基础的概念其变体和应用深不见底。从简单的打印节点到复杂的动态规划树形问题如树形DP遍历都是不可或缺的第一步。当你下次面对一棵“树”时无论是文件目录、组织架构还是算法题里的二叉树不妨先问自己我需要用什么顺序来访问它答案就在DFS、BFS、先序、中序、后序这几种经典的策略之中。
