★ FEATURED ARTICLE 二叉树的深度搜索问题也就是DFSDepth First Search在树结构上的应用是算法面试和刷题路上绕不开的高频考点。这一期“算法奇妙屋”第二十六期我就把二叉树DFS一次性讲透递归怎么写、迭代怎么写、经典题目怎么拆、坑在哪里顺便附上可以直接抄的代码和排查经验。如果你是刚开始学二叉树的新手这篇可以当入门地图用如果你在准备面试这篇也适合拿来做查漏补缺的系统整理。文章里我不会绕弯子直接上思路和代码遇到容易翻车的地方会专门标出来。1. 先把深度优先的本质讲透树为什么天然适合DFS1.1 树的递归结构决定了DFS是“本命遍历”二叉树这个数据结构有个很特别的地方它是递归定义的。一个节点有左子树和右子树左右子树本身又是一棵二叉树只是规模更小。这个特性意味着任何处理二叉树问题的思路只要你在某一个节点上想清楚“当前节点该做什么、左右子树该交给下一步做什么”整个问题就自动被拆成了规模更小的同类问题。这正是DFS最擅长的节奏。我经常跟朋友用一个迷宫的比喻深度优先搜索就像在迷宫里走一条路走到死胡同再回头换另一条岔路继续直到把所有路都探完。二叉树里没有死胡同但有叶子节点走到叶子就相当于探到底了这时候函数一层层返回就相当于从迷宫原路退回岔口。整个过程非常自然。再说清楚一点访问一个节点其实有三个时间点第一次到达它时、从左子树回来后、从右子树回来后。这三个时间点分别对应前序、中序、后序三种遍历方式。你只需要决定“在这个节点的哪个时机做你要做的事”就能写出不同行为的DFS。这也是为什么有的DFS题目要求你在到达节点时就判断逻辑有的却要求先算完子树再汇总。1.2 三种遍历顺序前序、中序、后序怎么选我把三种遍历的关键区别整理了一下面试前临时抱佛脚看这张表就够了遍历方式访问顺序典型使用场景前序遍历根节点、左子树、右子树拷贝树、序列化、从上到下构造、需要先处理当前节点再深入的情况中序遍历左子树、根节点、右子树二叉搜索树相关操作中序结果一定是有序数组后序遍历左子树、右子树、根节点求高度、删除节点、自底向上的汇总类问题实际做题时怎么选我的经验其实很粗暴如果当前节点的答案需要依赖左右子树的答案那就用后序如果当前节点可以直接决定答案左右子树只是往下走那就用前序涉及到二叉搜索树的有序性十有八九中序。举一个典型的例子求一棵二叉树的最大深度。深度这个值本质上是“左右子树深度的最大值再加1”所以必须先算出左右子树的深度再回到当前节点汇总这天然就是后序遍历的节奏。而如果你要判断一棵树是否对称你需要同时从根节点的左右两侧出发一边前序遍历一遍一边做镜像对比这时候前序的思路就更直接。1.3 深度优先和递归代码的对应关系很多人写DFS只记住了“用递归”却说不出为什么递归和DFS这么配。其实关键在于函数调用本身就是一个栈结构。当你调用一个函数时系统会把当前函数的状态压入调用栈等子函数返回之后再恢复现场继续执行。这个过程手动用栈模拟时叫做“回溯”由系统自动完成时就表现为递归。DFS需要探索一条路径到尽头再回退递归函数的调用和返回机制恰好就是“一路向下、原路返回”的执行模型。所以写递归版DFS你不需要自己维护栈只需要让函数自己调用自己。但这也带来一个隐患递归深度太大时系统调用栈会溢出。这个问题到后面第6章会专门讲现在先记住一个结论能够用递归写DFS是理解问题的最好起点但不是唯一实现方式。2. 递归写法别死记模板三要素拆解与返回值设计2.1 递归三要素终止条件、本层逻辑、递推方向我见过太多人背DFS模板背得滚瓜烂熟但一换题目就懵。原因很简单他们没有理解递归函数里真正要决定的三个东西。第一个是终止条件。放在二叉树里最常见的就是root null时返回因为空节点没有任何子树可以继续深入了。第二个是本层逻辑也就是当前这个节点在这一层要做什么操作是打印、是比较、还是累加第三个是递推方向你要想清楚调左子树还是右子树或者两个都调以及调用的结果要不要带回上一层。用一个最朴素的例子来感受一下前序遍历打印每个节点的值。def preorder(root): if root is None: return print(root.val) # 本层逻辑打印当前节点 preorder(root.left) # 递推方向向左深入 preorder(root.right) # 递推方向向右深入这段代码极其简单但三要素全在里面。空节点直接返回是终止条件打印是本层逻辑先左后右是递推方向。所谓DFS其实就是“在每一个节点上重复同一套决策”。2.2 经典案例求二叉树的最大深度最大深度是一道DFS入门绕不开的题。先看思路一棵树的最大深度就是根节点到最远叶子节点的路径上经过的节点数。这个定义一旦翻译成递归语言就变成了“当前节点的深度 1 max(左子树最大深度, 右子树最大深度)”。代码如下def max_depth(root): if root is None: return 0 left_depth max_depth(root.left) right_depth max_depth(root.right) return max(left_depth, right_depth) 1为什么这样写是对的因为递归会把问题拆给左右子树左子树告诉我们它有多深右子树告诉我们它有多深当前节点只需要选出较大的那一侧然后把自己这一层加进去。这就像你在公司里统计团队人数每个小组长汇报自己组的人数你把自己算上再加总这就是自底向上的汇总。这道题有个容易忽略的边界空树的最大深度是0。很多第一次写的人会把根节点为空的判断漏掉结果直接报空指针异常。边界情况永远是二叉树题目的第一个隐藏考点。2.3 返回值的“语义”先想清楚每层该给上层什么写DFS时最常见的卡壳点是“我不知道函数应该返回什么”。我建议你在写函数体之前先把这句话写出来我这个递归函数对于一棵子树要向上层返回什么信息不同的题目返回值的语义完全不同。求最大深度返回的是整数高度判断对称返回的是布尔值判断两棵树是否相同返回的也是布尔值而如果题目要你收集所有路径返回值可能是一个列表或者干脆不需要返回值只是把结果写进一个全局变量。举个例子求二叉树的最大路径和这里的路径不要求经过根节点也不要求从叶子出发而是一条任意节点连成的路径。这种题就不能单纯靠返回值搞定因为一个节点向上层能贡献的“单边最大值”和全局答案“路径和最大值”是两回事。通常的做法是递归函数返回“从当前节点出发向下能得到的最大单边路径和”同时用一个全局变量维护“当前子树里出现的最大路径和”。先想清楚语义再动手写代码能省下大量调试时间。我自己的习惯是在递归函数上面用注释写一行“返回XXX”然后才开始写实现这个习惯帮我在很多树上题目里避免过“返回值不知道给谁”的尴尬。3. 递归转迭代用栈手动模拟一遍DFS3.1 为什么面试官总爱问“非递归实现”递归版DFS写起来爽但面试官特别喜欢问一句“如果不让用递归你会怎么写”这个问题背后的动机不只是考察你栈的数据结构掌握程度更是在确认你是否真的理解DFS的执行过程。如果树的深度很大尤其是退化成一条链时递归调用栈的深度会等于节点数程序很容易栈溢出。另一方面有些语言和运行环境对递归深度有明确限制写递归前你得心里有数。手动用栈模拟DFS虽然代码会比递归长一点但栈的大小是自己在堆上管理的可控性更好。还有一点用栈模拟是理解“回溯”概念的捷径。递归版本里系统自动帮你恢复现场迭代版本里你得亲手把状态压栈、取出、再恢复这个过程走过一遍之后你对DFS的认识会从“照着写”变成“真懂了”。3.2 前序遍历迭代栈的入栈顺序是关键前序遍历的顺序是“根、左、右”。用栈模拟时因为栈是后进先出所以你想先访问左子树就得先把右子树压入栈再把左子树压入栈。这样弹出时才会先弹左子树。def preorder_iter(root): if root is None: return [] res [] stack [root] while stack: node stack.pop() res.append(node.val) if node.right: stack.append(node.right) # 右子树先入栈 if node.left: stack.append(node.left) # 左子树后入栈但后入先出所以先被访问 return res这段代码虽然短但你最好自己手动模拟一遍。假设现在的树是1 - 左2 - 右3根节点1先弹出往结果里塞1然后右3入栈、左2入栈下一轮弹出2访问2再下一轮弹出3访问3。最终结果就是1、2、3和前序遍历一致。3.3 中序与后序迭代这里容易写错中序遍历的迭代比前序要难一点关键在于“一路向左弹栈访问再转向右”。def inorder_iter(root): res [] stack [] cur root while cur is not None or stack: while cur: stack.append(cur) cur cur.left node stack.pop() res.append(node.val) cur node.right return res这段代码的思维模式和前序完全不同前序是“弹出就访问”中序是“先压到底弹出来再访问”。很多人在cur node.right这一步漏写或者写成cur node导致死循环。注意访问完当前节点后下一步要去的是右子树而不是回到父节点。后序遍历迭代有好几种写法。最简单的一种是“变体前序再反转”先按“根、右、左”的顺序访问然后把结果反转成“左、右、根”。def postorder_iter(root): res [] if root is None: return res stack [root] while stack: node stack.pop() res.append(node.val) if node.left: stack.append(node.left) if node.right: stack.append(node.right) return res[::-1]为什么这招有效正常前序是“根左右”我们改成“根右左”也就是先访问根再优先向右探索。把这样的访问序列反转就正好得到“左右根”——也就是后序遍历。这个技巧实战里非常好用面试手写时也快。3.4 迭代DFS的时间空间复杂度变化不管是递归还是迭代DFS的时间复杂度都是O(n)因为每个节点恰好被访问一次。这里的n是节点总数。空间上有区别。递归版本的空间复杂度取决于递归调用栈的深度最坏情况下等于树的高度h当树退化成链表时h等于n所以空间是O(h)。迭代版本显式使用栈栈里最多同时存放一条路径上的节点同样也是O(h)。换句话说两者在空间复杂度上并没有质的差别迭代的真正优势是“栈在堆上分配”比系统调用栈更抗压以及方便手动控制而不是空间复杂度更低。这里给你一个真实的比较表格实现方式时间空间栈溢出风险代码可读性递归O(n)O(h)高系统调用栈高贴近问题本质迭代O(n)O(h)低堆上栈中低需要理解过程4. 4道必练的DFS实战题题题都有坑4.1 最大深度先解决空树边界最大深度的递归写法上面已经给过了这里补充一个很多人忽略的测试习惯写完之后至少用三个用例验证空树、单节点树、普通三层二叉树。空树返回0单节点返回1三层树正常累加。其实在处理任何二叉树题目时这三个输入都应该是默认的自测用例。如果你想顺手练一下迭代版本可以用前序遍历的栈结构在每个节点入栈时同时记录它的深度。弹出一个节点时更新最大深度然后左右孩子分别带深度1入栈。这也是一种DFS实现而且不需要额外递归。def max_depth_iter(root): if root is None: return 0 stack [(root, 1)] max_d 0 while stack: node, depth stack.pop() max_d max(max_d, depth) if node.left: stack.append((node.left, depth 1)) if node.right: stack.append((node.right, depth 1)) return max_d4.2 最小深度直接套最大深度会翻车最小深度这个题表面上看把max改成min就行了实际上不是。最小深度要求的是“从根节点到最近叶子节点的路径上的节点数”关键在于叶子节点的定义是左右孩子都为空的节点。如果把空节点的高度当成0很容易在树只有单边子树时算错。比如一棵树只有根和左孩子没有右孩子最小深度是2但如果你直接写成1 min(minDepth(root.left), 0)会得到1这显然不对。因为根节点的右子树为空意味着不存在“从根到右次叶子”的路径你不能把空的那一侧当成一条深度为0的合法路径。正确写法是要区分三种情况def min_depth(root): if root is None: return 0 if root.left is None and root.right is None: return 1 if root.left is None: return min_depth(root.right) 1 if root.right is None: return min_depth(root.left) 1 return min(min_depth(root.left), min_depth(root.right)) 1记住这个坑空树深度0叶子节点深度1单边为空时只能沿着非空的一侧继续往下找不能拿0来凑。4.3 对称二叉树镜像递归要两个指针判断一棵二叉树是否对称指的是它是否和自己的镜像相同。关键思路是递归函数需要同时接收两个参数一个指向左子树的节点一个指向右子树的节点这两个节点需要满足镜像相等关系。终止条件有两层。第一层两个指针都为空说明这一对镜像分支到底了返回True第二层一个为空一个不为空说明结构不对称返回False。然后比较两个节点的值是否相等再递归对比“左边的左子树 和 右边的右子树”以及“左边的右子树 和 右边的左子树”。def is_symmetric(root): if root is None: return True return check(root.left, root.right) def check(left, right): if left is None and right is None: return True if left is None or right is None: return False if left.val ! right.val: return False return check(left.left, right.right) and check(left.right, right.left)这里最容易犯的错是只对比左右孩子节点本身忘了继续递归对比它们的内外侧子树。题目考对称比的是整体结构不是一层结构。4.4 路径总和DFS带回溯语义路径总和这个题目非常经典给定一个目标值判断是否存在一条从根节点到叶子节点的路径使路径上所有节点值之和等于目标值。解法思路是从根往下走每经过一个节点就用目标值减去当前节点值走到叶子时检查剩余值是否刚好减成0。注意叶子节点的定义一定是左右孩子都为空的节点。def has_path_sum(root, target_sum): if root is None: return False target_sum - root.val if root.left is None and root.right is None: return target_sum 0 return has_path_sum(root.left, target_sum) or has_path_sum(root.right, target_sum)用“剩余值递减”的方式写比“当前累加值加目标值比较”要简洁同时少传一个参数。这个题目常被拿来和“回溯”结合升级接下来的第五章就是处理“收集所有路径”这类进阶变体。5. 进阶回溯与剪枝处理路径收集类问题5.1 回溯其实就是DFS的“恢复现场”如果你能写出路径总和那下一步自然是“输出所有满足条件的路径”。这时候就不再是简单的返回值传递了而是需要在DFS过程中维护一条正在探索的路径把沿途节点记录下来满足条件时整条路径存入结果列表。问题在于如果在递归里直接往列表加节点递归返回时如果不删掉路径就会越攒越长把不是当前路径的节点也带进去。所以每次递归结束后要把自己从路径列表里移除这就是“恢复现场”也就是回溯。def path_sum(root, target_sum): res [] path [] def dfs(node, remain): if node is None: return path.append(node.val) remain - node.val if node.left is None and node.right is None and remain 0: res.append(path[:]) else: dfs(node.left, remain) dfs(node.right, remain) path.pop() dfs(root, target_sum) return res有个细节值得单独说把路径存入结果时为什么要写path[:]而不是直接res.append(path)因为path后面还会被继续修改直接append会把同一个可变对象引用存进去最后res里的所有路径都会变成同一个列表。path[:]相当于复制当前路径的快照。5.2 剪枝技巧什么条件下能提前返回剪枝的意义在于当子树已经没有可能产生答案时就不要继续往下走了。它和回溯经常成对出现回溯负责保证正确性剪枝负责提速。最典型的情况是如果所有节点值都是正数那么当路径累积和已经超过目标值时再往下走只会越来越大不可能再等于目标值可以直接返回。这一类剪枝写起来很简单if remain 0 and all values positive: return但必须强调前提条件如果节点值可能为负数这个剪枝就不能用。负数的存在会让路径和出现先大后小的情况当前超过目标值不代表后续不会减回目标值。判断能不能剪枝要先看数值特性不能无脑套模板。还有一类剪枝和结构有关。比如题目限制“路径长度不超过k”那递归时就可以把剩余深度作为参数剩余深度小于0时直接返回。这类剪枝虽然不改变最坏时间复杂度但在实际数据上提速非常明显。5.3 从DFS到记忆化避免重复计算二叉树上的DFS问题严格来说子问题不会重复因为每个子树在递归树里只出现一次。但有一种情况会让你重复计算递归函数里同时在做“子树搜索”和“子树属性计算”导致同一个子树被反复遍历。我举一个典型的例子求二叉树中最长路径长度直径。直径的定义是任意两个节点之间路径的最大长度这个长度可以通过“左子树高度右子树高度”来算。很多人第一版写成了这样在搜索每个节点时调用一次求高度的函数求高度本身又是一次完整的后序遍历于是每个节点都被重复访问了很多次整体复杂度从O(n)退化成了O(n²)。正确的做法是用一次后序遍历同时完成“算高度”和“更新直径”两件事def diameter_of_binary_tree(root): max_diameter 0 def height(node): nonlocal max_diameter if node is None: return 0 left_h height(node.left) right_h height(node.right) max_diameter max(max_diameter, left_h right_h) return max(left_h, right_h) 1 height(root) return max_diameter这个例子提醒我们DFS里不要轻易做“重复遍历同一棵子树”的事。设计递归函数时尽量让一次DFS同时承担多个职责。如果确实存在子问题重叠的树形场景则可以考虑在递归函数里加缓存用节点本身作为key去记忆化。6. 高频报错与排查实录从栈溢出到重复计算6.1 栈溢出当树退化成长链我前面提到过递归版DFS的栈深度等于树高。如果这棵树是平衡的高度是log n级别没什么问题但如果它退化成了近似链表的结构比如每个节点都只有右孩子那树高就约等于节点数。这种输入下递归深度轻松上万系统调用栈直接崩掉。怎么定位这类问题第一看报错堆栈如果栈信息显示在DFS递归函数的同一行反复出现几千次基本可以断定是递归深度过大。第二看时间点栈溢出往往发生在输入数据量很大且树结构是长链的时候。解法也很直接换迭代版栈模拟把递归的调用栈换成在堆上维护的显式栈这就能绕开系统栈深度的限制。6.2 空指针与边界条件最常见的低级错误二叉树问题里空指针异常是新手最容易碰到的错误而且报错位置经常很晚才暴露。比如你想判断当前节点是否有左孩子直接写了if root.left.val ...但root本身都可能是空那就直接崩了。我的排查习惯是任何涉及root.left或root.right的访问先想清楚root是否可能为空任何递归入口先处理root is None的情况。写完之后用空树和单节点树作为第一组测试数据能过滤掉大部分低级错误。顺便提一个判断叶子节点的常见误区有人把叶子条件写成node is None这是错的。叶子节点是“左右孩子都为空的非空节点”不是空节点。空节点本身不能当叶子它们没有被算作合法路径终点。6.3 超时与重复计算性能排查思路如果DFS代码逻辑正确但提交时超时九成是复杂度出了问题。最常见的原因是递归函数内部又调用了另一个递归函数造成同一棵子树重复遍历。我之前见过一个实现判断二叉树是否平衡时每层都调一次求高度函数然后再递归判断左右子树是否平衡。从表面看逻辑没错但总时间复杂度变成了O(n log n)在深度较大的树形数据上就会超时。正确的优化思路是让“高度计算”和“平衡性判断”合并到同一次后序遍历里递归返回时既向上一层报告当前高度也顺手判断当前子树是否平衡。如果不平衡用特殊返回值或全局标记来提前终止后续递归就无需继续了。症状可能原因排查方向空指针异常没有处理空节点检查递归入口是否判空结果偏小/偏大叶子节点判断错误确认叶子是左右孩子都为空超时重复遍历子树检查是否在递归内部重复调用高度函数栈溢出树高过大导致递归过深换迭代栈实现返回所有路径都相同直接append了可变列表用path[:]保存快照我个人在做二叉树DFS时习惯先在纸上画出递归树把每个节点的“返回值是什么”标注在旁边然后再写代码。这个方法听起来老土但真的能提前暴露很多逻辑漏洞。另外一个小技巧在递归函数开头用注释写清楚“这个函数返回什么、参数含义、终止条件”比事后打日志调试高效得多。如果这篇二叉树的DFS总结能帮你在面试或刷题时少走点弯路那这一期的整理就值了。下一篇“算法奇妙屋”打算聊二叉树DFS的进阶变体比如二叉树的序列化与反序列化、最近公共祖先这类高频题到时候我们接着往下拆。
阅读完成 · 觉得有帮助？
