这周训练营一下子塞了五道二叉树题进来乍一看像是要刷吐的量但静下心把这些题摆在一起观察会发现它们其实是同一套递归逻辑换了几件马甲翻转一棵树、判断对称、数深度、数节点。只要你掌握“递归出口、遍历顺序、返回值设计”这三点这五道题一晚上就能全部吃透。这篇把我自己刷题时的思路、踩过的坑、迭代和递归两种写法的取舍都整理出来给正在跟着训练营节奏走、或者刚开始刷二叉树的朋友做个参考。1. 先把这5道题的骨架看穿递归出口、遍历顺序、返回值设计1.1 递归三步法不是背代码而是先定接口很多同学刷树的时候容易直接看题解然后把代码抄一遍、跑一遍觉得会了。但过几天再遇到类似题又忘记了。原因很简单你没有把递归的“接口”想清楚。我不太喜欢直接背模板而是习惯拿到一道树的递归题先问自己三个问题这个函数要返回什么是节点、布尔值还是数字什么时候可以停止递归也就是 null、叶子节点这些边界情况怎么处理。当前这一层的“活”是什么我要不要操作这个节点还是先等左右子树的结果返回再说这三个问题想明白代码就等于写完一半了。拿上面这五道题套一下翻转二叉树返回的是翻转后的根节点当前层的活是交换左右孩子。对称二叉树返回的是“是否相等”的布尔值当前层的活是比较两个节点的值。最大深度返回的是高度值当前层的活是取左右高度的最大值再加 1。最小深度返回的也是高度值但终止条件比最大深度苛刻必须遇到叶子节点才算到底。节点个数返回的是数量当前层的活是左子树数量 右子树数量 1。看到规律没有除了对称二叉树大部分题目都是标准的“后序遍历”先把左右子树的结果算出来然后回到根节点做一个汇总。这其实不是一个巧合因为树本身就是递归定义的一棵树的高度、节点数量这类属性天然需要依赖子树的信息。1.2 这5道题分别属于哪类遍历我再把遍历顺序这个维度掰开揉碎讲一下。二叉树遍历的基础是前序、中序、后序、层序你做某件事的时机决定了代码长什么样。题目推荐遍历顺序为什么是这个顺序翻转二叉树前序 / 后序交换左右孩子的动作既可以先做也可以后做结果一致对称二叉树后序本质上是两棵子树成对递归需要拿到左右两个子树的比较结果二叉树的最大深度后序深度是从叶子向上汇总的二叉树的最小深度后序 / 层序后序要注意叶子定义层序碰到第一个叶子直接返回完全二叉树的节点个数后序节点的数量必须由左右子树累加而来我早期刷题有个误区总是想找“最牛的解法”或者“最短的写法”后来发现对新手来说最快的进步方式是先把最自然的写法写对再去谈优化。深度这种题就是非常好的例子你不需要一上来就背层序遍历模板先把递归写顺了再去看迭代。2. 翻转二叉树与对称二叉树成对镜像其实是一体两面2.1 翻转二叉树前序还是后序都行中序别用翻转二叉树是个很“直观”的题。给你一棵树把每个节点的左右孩子交换整棵树就左右镜像了。我推荐直接用递归。核心代码就一句话交换当前节点的左右子树然后递归地翻转左、右子树。var invertTree function(root) { if (root null) return null; [root.left, root.right] [root.right, root.left]; invertTree(root.left); invertTree(root.right); return root; };注意这里我用了数组交换的写法[root.left, root.right] [root.right, root.left]JavaScript 里很舒服不需要引入第三个临时变量。上面这种写法是前序先交换再递归。其实把交换放在递归后面也完全没问题var invertTree function(root) { if (root null) return null; invertTree(root.left); invertTree(root.right); [root.left, root.right] [root.right, root.left]; return root; };这是后序先递归处理左右子树最后交换。两种跑出来的结果一样因为每个节点都会被访问一次交换动作放在前面还是后面不影响最终结构。特别提醒不要写中序遍历的版本也就是“先翻转左子树、交换左右孩子、再翻转右子树”。这样会导致某些子树被翻转两次结果完全错误。这不是一个好玩的坑初学阶段没必要去踩。如果你不想用递归也可以用栈模拟前序遍历var invertTree function(root) { if (root null) return null; const stack [root]; while (stack.length) { const node stack.pop(); [node.left, node.right] [node.right, node.left]; if (node.left) stack.push(node.left); if (node.right) stack.push(node.right); } return root; };这种迭代写法的好处是不会有递归栈溢出的风险适合处理特别深的树。但日常面试或刷题我一般先写递归更快也更稳。翻转这道题的核心收获树的结构修改题往往就是遍历到每个节点然后在当前层做一次操作。2.2 对称二叉树递归比较的是“左右两棵子树”对称二叉树比翻转稍微绕一点。翻转是对单棵树做修改而对称是要判断“一棵树的左右子树是不是互为镜像”。递归的入口就不是一个节点而是两个节点root.left和root.right。这也是为什么很多初学者卡住的地方——你没法只写一个节点的递归去判断对称因为镜像的比较必须成对出现。先看递归写法var isSymmetric function(root) { if (root null) return true; const compare (left, right) { if (left null right null) return true; if (left null || right null) return false; if (left.val ! right.val) return false; return compare(left.left, right.right) compare(left.right, right.left); }; return compare(root.left, root.right); };递归函数里的两条比较路径要特别注意compare(left.left, right.right)比较左子树的左孩子和右子树的右孩子。compare(left.right, right.left)比较左子树的右孩子和右子树的左孩子。这就是“镜像”两个字的意义。你站在一颗镜子面前你的左手对应镜子里你的右手左手左脚都要反过来比。终止条件的写法是这道题的精髓两个都是 null说明这一对分支到底了是对称的返回 true。一个 null 一个不是 null说明结构不对称返回 false。两个值不相等内容不对称返回 false。否则继续递归。我当时第一次写的时候漏掉了left.val ! right.val这个判断结果结构相同的树不管值是不是相等都返回 true。这个错误如果不在测试用例里跑一下光靠看很难发现。也可以用迭代的写法用队列每次取两个节点成对比较var isSymmetric function(root) { if (root null) return true; const queue [root.left, root.right]; while (queue.length) { const left queue.shift(); const right queue.shift(); if (left null right null) continue; if (left null || right null) return false; if (left.val ! right.val) return false; queue.push(left.left); queue.push(right.right); queue.push(left.right); queue.push(right.left); } return true; };注意这里入队的顺序有讲究left.left和right.right成一对left.right和right.left成一对。这样每次从队头拿出两个节点正好是需要比较的镜像位置。2.3 两道题放一起的原因调用参数不同导致代码迥异把翻转和对称放在同一天刷我觉得训练营是有意的。翻转树是“一棵树内部的操作”递归函数永远只接收一个节点操作对象是这个节点的左右孩子。对称则是“两棵树之间的比较”递归函数接收两个节点比较的是一个节点的孩子和另一个节点的孩子。这两道题合在一起能帮你建立一个很重要的意识递归函数的参数列表取决于你要比较或操作的“对象是什么”。如果一个判断需要跨树比如对称、合并二叉树参数往往就是两个如果一个操作只针对单棵树参数通常是一个。很多同学看完题解会觉得懂了但下次遇到对称那个题还是写不出就是因为没有建立这个“双参数递归”的意识。你自己动手在纸上画一棵树模拟一下递归的调用顺序比看十遍视频都有用。3. 最大深度与最小深度一字之差差在叶子判断3.1 最大深度后序汇总的模式很好用二叉树的最大深度也叫高度是最经典的递归入门题。递归思路非常自然一棵树的高度 max(左子树高度, 右子树高度) 1空树高度为 0。直接写var maxDepth function(root) { if (root null) return 0; return Math.max(maxDepth(root.left), maxDepth(root.right)) 1; };就这么点代码。递归到叶子下面一层时左右子树返回 0叶子节点返回 1 往上逐层累加。除了递归层序法也可以求最大深度。层序就是一层一层往下走每走一层深度加 1var maxDepth function(root) { if (root null) return 0; const queue [root]; let depth 0; while (queue.length) { let size queue.length; while (size--) { const node queue.shift(); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } depth; } return depth; };这个写法本质上就是 BFS每次把当前层全部弹出再压入下一层。如果你已经把层序遍历的模板背熟了这题也可以直接用层序遍历写但递归版显然更简洁。3.2 最小深度递归的坑与 BFS 的天然优势最大深度好写最小深度陷阱就来了。很多人第一反应是把最大深度的Math.max换成Math.min// 错误写法别学 var minDepth function(root) { if (root null) return 0; return Math.min(minDepth(root.left), minDepth(root.right)) 1; };这代码看着像对称的解法实际是错的。比如一棵树只有左子树、没有右子树1 - 2 - 3 - 4 - 5这种高度 5 的单链表型二叉树当你走到根节点时右子树是 nullminDepth(null) 0于是根节点的最小深度被算成 1。这显然不对因为最小深度是从根到“最近叶子”的距离null 不是叶子。正确的递归思路是如果当前节点是叶子左右孩子都为 null返回 1。如果只有一个孩子说明只能沿着这个孩子继续走返回那个方向的最小深度 1。如果有两个孩子才取两者较小值加 1。写成代码var minDepth function(root) { if (root null) return 0; if (root.left null root.right null) return 1; if (root.left ! null root.right null) { return minDepth(root.left) 1; } if (root.left null root.right ! null) { return minDepth(root.right) 1; } return Math.min(minDepth(root.left), minDepth(root.right)) 1; };还有一个很巧妙的精简写法如果你理解了“单孩子分支取另一边”的原理可以用Math.max来处理单孩子的情况var minDepth function(root) { if (root null) return 0; if (root.left null || root.right null) { return Math.max(minDepth(root.left), minDepth(root.right)) 1; } return Math.min(minDepth(root.left), minDepth(root.right)) 1; };当只有一个孩子时另一边的深度是 0用max(0, 另一边深度)就正好取到了那个不为空的子树。这个写法的确很巧妙但如果你第一次理解不了建议先老老实实写分支判断不要为了短而短。相比之下层序法求最小深度就非常舒服从上到下逐层遍历遇到第一个叶子节点直接返回当前深度。因为 BFS 天然是从近到远搜索第一次遇到的一定是最浅的叶子。var minDepth function(root) { if (root null) return 0; const queue [root]; let depth 1; while (queue.length) { let size queue.length; while (size--) { const node queue.shift(); if (node.left null node.right null) { return depth; } if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } depth; } return depth; };注意 BFS 里深度初始值是 1不是 0因为根节点本身就算一层。3.3 什么时候更推荐层序什么时候用递归求深度这道题很好地展示了 DFS 和 BFS 的取舍。我个人的建议是最大深度递归最干净直接用Math.max 1。最小深度层序更直观遇到叶子就返回递归也能写但必须处理叶子边界。如果面试官要求写迭代优先层序因为层序的代码模式和口头解释都很自然。写法最大深度最小深度递归后序推荐代码极短可以但易踩叶子判断的坑层序 BFS可以代码稍长推荐遇到第一个叶子直接返回前序 全局变量可以和递归类似也要处理叶子这里我想强调一个刷题策略不要只背一种解法。同样的题递归写一遍层序再写一遍你对树的遍历结构理解会深很多。4. 完全二叉树的节点个数不只是遍历还能用性质剪枝4.1 朴素递归所有二叉树通用的解法如果题目没有任何附加条件就是给你一棵普通二叉树让你数节点那么最简单的方法就是递归遍历var countNodes function(root) { if (root null) return 0; return countNodes(root.left) countNodes(root.right) 1; };这个解法的时间复杂度是 O(n)你需要把整棵树每个节点都走一遍。这个版本必须会写因为它对任意二叉树都是正确的而且代码量几乎等于没有。但既然题目给了“完全二叉树”这个前提我们就可以聪明一点利用它的性质把时间复杂度往下降。4.2 利用完全二叉树“左深不小于右深”的性质完全二叉树的定义是除了最后一层其余层都是满的并且最后一层的节点都靠左排列。这个定义带来一个关键性质从某个节点出发沿着最左侧走的深度一定不小于沿着最右侧走的深度。如果两者相等说明这棵子树是一棵满二叉树。为什么因为最后一层节点是靠左排列的所以左边可能比右边多一层但右边不可能比左边多一层。当最左路径的深度等于最右路径的深度时说明最后一层已经填满了没有任何缺口整棵子树是满二叉树。满二叉树的节点个数可以直接用公式计算2^height - 1其中 height 是子树的高度。所以优化思路就出来了计算从当前节点出发一路向左的深度。计算从当前节点出发一路向右的深度。如果两者相等用公式返回节点数。如果不相等就递归计算左子树和右子树再加 1。var countNodes function(root) { if (root null) return 0; let leftDepth 0; let left root.left; while (left) { leftDepth; left left.left; } let rightDepth 0; let right root.right; while (right) { rightDepth; right right.right; } if (leftDepth rightDepth) { return Math.pow(2, leftDepth 1) - 1; } return countNodes(root.left) countNodes(root.right) 1; };这里leftDepth是从当前节点的左孩子一路向左走到的边数所以当前子树的整体高度是leftDepth 1节点数就是2^(leftDepth 1) - 1。代码里用Math.pow(2, leftDepth 1)或者2 ** (leftDepth 1)都可以。复杂度是多少每次递归都会走一段 while 循环来计算深度这段循环的代价是 O(log n)。而递归的深度也是 O(log n)因为每次递归调用问题的规模都会减半实际上至少有一侧子树是完全的可以直接用公式。所以总复杂度是 O((log n)^2)。这个优化在大数据量下非常明显。面试时如果遇到这题完全可以说出两种写法先写 O(n) 遍历再提这个完全二叉树性质的优化。经验谈JavaScript 里不要写(1 height)这种位运算求 2 的幂因为位运算只对 32 位整数生效树高稍大一点就会结果异常。优先用**运算符或Math.pow。4.3 什么时候用“递归公式”什么时候直接遍历这里要特别提醒一句上面的优化只有在“完全二叉树”的前提下才成立。如果输入是普通二叉树左右子树深度相等也不代表它是满二叉树节点数不能用公式直接算。所以做题前先读题看清是 complete binary tree 还是 binary tree。如果只说二叉树老老实实 O(n) 遍历不要为了炫技把前提搞错。另外还有一个细节完全⼆叉树的递归计算里leftDepth rightDepth判断的是“从当前节点出发最左和最右的深度一致”。对于普通完全二叉树大部分递归路径都会在某一层走到满二叉树然后提前返回。这个递归不会遍历所有节点这也是它比朴素递归快的原因。5. 排查手册这5道题我踩过的四个坑5.1 把“空节点”当成了“叶子节点”这个坑主要集中在最小深度。null是空指针不是叶子。叶子指的是左右孩子都为 null 的节点。最小深度必须走到叶子才能停止递归。如果你拿if (root null) return 0作为递归出口然后用Math.min(...)汇聚单支树就会算错。解决办法写最小深度前先在草稿纸上画一棵只有左孩子或只有右孩子的树手动走一遍递归确认每个分支的返回值。5.2 递归出口漏掉“值不等”的判断对称二叉树里很多人判断完两个节点是否为空后直接就递归比较了忘了比较left.val和right.val是否相等。这样导致的结果是两棵树结构完全对称但节点的值完全不同也被判定为对称。这个错误特别隐晦因为小的测试用例可能恰好值也一样代码跑一遍通过了你就以为写对了。多构造几个不对称值的用例试试比如[1,2,2,3,4,4,5]。5.3 迭代层序时没有缓存队列长度这是层序遍历最容易犯的错。我见过很多同学这样写// 错误写法 for (let i 0; i queue.length; i) { const node queue.shift(); // ... }问题在哪queue.length是动态变化的你在循环里不断shift()和push()循环变量i的临界条件会漂移导致当前层和下一层的节点混在一起。正确做法是在进入一层之前先把当前层的节点数存下来let size queue.length; while (size--) { const node queue.shift(); // ... }这样处理完size个节点后队列里剩下的就全是下一层的节点了。5.4 JavaScript 数组shift()的性能坑严格来说数组shift()的时间复杂度是 O(n)因为它要移动后面的所有元素。如果树的节点特别多层序法用shift()会让整体性能变差。刷题时可以接受但如果写生产代码或者遇到极大数据量的测试用例建议用指针来模拟队列const queue [root]; let index 0; while (index queue.length) { const node queue[index]; if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); }这样出队只是移动下标不会反复搬移数组元素。最大深度、最小深度、层序翻转都可以用这个姿势。5.5 递归不画调用树凭感觉写最后一个不算 bug而是方法论的问题。树相关的递归尤其是对称、最小深度这种有多个分支的如果光靠脑子脑补特别容易漏掉某个分支或者写错终止条件。我在刷题时会随手画一棵只有两三层的小树手动把递归调用展开一遍。比如对称二叉树画一个三层满树看compare(left.left, right.right)和compare(left.right, right.left)这两条分支到底走的是哪些节点走两遍之后代码为什么这样写就刻进脑子里了。写在最后二刷这五道题时我最大的感受是它们并不需要死记硬背真正要理解的是三件事——递归出口怎么写、当前层要做什么、该用前序还是后序。想明白这三件事翻转、深度、节点数都可以在极短的代码里写出来对称二叉树多一个“双参数递归”的意识也不会再卡壳。建议你可以把这五道题按“后序模板”分组再刷一遍后序遍历改一改返回值能同时解决最大深度、最小深度、节点个数、对称二叉树的大部分逻辑翻转二叉树则单独体会一下前序和后序没有本质区别。最后再用层序刷一遍深度和翻转两套思路都过完这些题就真正内化了。
