做前端这些年要说算法题里哪类题目最常被问、也最能看出基本功js 二叉树的DFS和BFS绝对排得上号。很多同事一提到就头疼递归怎么老是绕晕迭代写法为什么就是背不下来BFS又该什么时候用我在实际业务里处理树形菜单、组织架构、递归组件渲染时发现这些概念其实没那么玄乎关键是把底层的遍历逻辑彻底搞明白。这篇内容就是我整理出的完整思路从节点定义开始到DFS的三种顺序、迭代写法、BFS层序遍历再到真实场景里怎么用最后把我踩过的运行时错误一并讲清楚希望对准备面试或者刚接触树形数据处理的同学有实实在在的帮助。1. 先看明白二叉树在JS里到底是什么节点的定义与递归思维1.1 LeetCode风格的节点定义在JavaScript里二叉树没有一个原生类型它完全靠普通的对象或类来模拟。最常用的方式就是LeetCode上的定义function TreeNode(val, left, right) { this.val (val undefined ? 0 : val); this.left (left undefined ? null : left); this.right (right undefined ? null : right); }这段代码的逻辑很简单每个节点最多有三个信息——自己的值val、左子节点left、右子节点right。left和right如果没传默认就是null也就是没有那个分支。实际构建一棵树的时候你会看到这种层层套娃的写法const root new TreeNode(1); root.left new TreeNode(2); root.right new TreeNode(3); root.left.left new TreeNode(4); root.left.right new TreeNode(5);这棵树长这样1 / \ 2 3 / \ 4 5很多新手有个误区以为树本身是一个对象其实它是由多个TreeNode通过指针串起来的结构。你手头拿到的root只是入口节点顺着left和right才能摸到整棵树。这也是为什么DFS和BFS都必须从root开始一层层、一条条地访问。1.2 二叉树常见形态普通树、满二叉树、完全二叉树、搜索二叉树虽然我们写算法时默认处理的是普通二叉树但了解几个常见变体很有用满二叉树每个非叶子节点都有左右两个子节点所有叶子节点在同一层。完全二叉树除最后一层外每层都被填满最后一层节点从左到右排布。二叉堆就是完全二叉树。搜索二叉树BST对于任意节点左子树所有节点值都小于它右子树所有节点值都大于它。BST有一个很关键的性质中序遍历结果一定是升序排列的。所以我每次看到验证搜索二叉树的题第一反应就是跑一遍中序遍历。线索二叉树利用空指针存储前驱和后继节点信息目的是让遍历不需要递归或栈。这个在实际面试里相对少考面试重点是前三种。1.3 为什么说递归是理解二叉树的钥匙二叉树的结构本身就是递归的一个节点包含两个更小的二叉树。你用过递归渲染组件吗前端渲染树形菜单的时候每个菜单项的children就是一棵子树递归组件对children调用自身这就是DFS的思路。反过来如果你试图用一个数组去模拟这种嵌套关系就得手动维护层级索引非常繁琐。所以处理二叉树的第一个思维转变是不要试图用脑子记住一整棵树的形状而是只关注当前节点和它的左右子树。所有DFS递归写法本质上都在回答三个问题当前节点要不要处理处理完去左子树还是先右子树这三个问题排列组合演化出了前序、中序、后序三种遍历方式。2. DFS递归版前序、中序、后序到底在输出什么2.1 三种遍历的本质是根节点被访问的时机DFS深度优先搜索的核心是一条路走到黑再回头走另一条。在二叉树上它天然对应前序、中序、后序三种遍历区别只在于根节点.val的访问时机前序遍历根 - 左 - 右。先处理当前节点再去递归左子树和右子树。中序遍历左 - 根 - 右。先递归左子树处理完再访问当前节点最后递归右子树。后序遍历左 - 右 - 根。左右子树都递归完了最后才访问当前节点。很多人记不住这三种顺序我的口诀是看根跑到哪里。前序根最前面中序根在中间后序根在最后。记住这个写代码时只挪一行console.log的位置就够了。2.2 三个递归实现的代码对比// 前序先处理自己再遍历孩子 const preorder (root) { if (!root) return; console.log(root.val); preorder(root.left); preorder(root.right); }; // 中序先遍历左孩子再处理自己最后右孩子 const inorder (root) { if (!root) return; inorder(root.left); console.log(root.val); inorder(root.right); }; // 后序先遍历孩子最后处理自己 const postorder (root) { if (!root) return; postorder(root.left); postorder(root.right); console.log(root.val); };用前面那棵树跑一下结果分别是前序1, 2, 4, 5, 3中序4, 2, 5, 1, 3后序4, 5, 2, 3, 1你可以自己在纸上对一下前序第一个必然是根节点1中序中1左右分别是左子树和右子树的节点后序最后一个必然是根节点1。这三个特征在面试里经常用来反推二叉树结构比如给前序中序重建二叉树本质上就是利用前序找根中序分割左右。2.3 递归一定要有出口而且要在进入函数的第一行这是我带过很多新人后最深的一个体会。递归函数第一件事必须是判断当前节点是否为空如果是就直接return。少写这个判断或者写错位置就会出现两种情况要么无限递归下去直到爆栈要么在null节点上访问.val直接抛TypeError。为什么递归能自动结束因为每调用一次树的规模就变小一点直到遇到null叶子节点函数开始往回返回。所以if (!root) return这个出口是整个递归能否收敛的钥匙。我看到很多人喜欢在调用处加判断比如if (root.left) preorder(root.left)这样也可以但函数内的空判断仍然建议保留因为它是兜底方案。提示递归写的不是怎么走到终点而是每一层节点要做什么事。如果发现自己写的递归函数一直在往外抛null错误先检查出口条件是不是写在了访问节点属性之后的代码里。3. 迭代版DFS用显式栈模拟递归顺便解决栈溢出焦虑3.1 为什么要学迭代写法递归虽然简洁但有一个致命问题它是靠函数调用栈来实现的每递归一层就压一个栈帧。二叉树如果退化成了链状每个节点只有一个子节点深度就是节点数比如几万个节点递归直接抛出Maximum call stack exceeded。除了这个问题很多面试官也会问你能用迭代实现前序遍历吗考察的就是对栈这种数据结构的理解。迭代写法的思路很直接递归里隐藏的栈我们自己用一个数组模拟出来。JavaScript里数组的push和pop天然就是栈操作。3.2 前序遍历的栈写法const preorderTraversal (root) { if (!root) return []; const stack [root]; const result []; while (stack.length) { const node stack.pop(); result.push(node.val); if (node.right) stack.push(node.right); if (node.left) stack.push(node.left); } return result; };这里有个细节值得展开说一下为什么先压right再压left因为栈是后进先出我们要保证左子树先被弹出处理就必须让左子树后进栈。所以入栈顺序和访问顺序是反的。很多新手在这里写反输出就变成了根右左而不是根左右。判断方法很简单在while循环里打印每次pop出来的值跟着纸上走一遍就能发现问题。3.3 中序遍历的指针栈写法中序迭代是三种遍历里最容易绕晕的因为它不能简单地根先入栈再调整顺序。中序要求先输出最左边的节点所以我们要用一个指针cur不断向下找左孩子沿途把节点压栈直到cur为null说明已经走到子树的最左边这时候弹出栈顶节点输出然后让cur指向该节点的右子树。const inorderTraversal (root) { const result []; const stack []; let cur root; while (cur || stack.length) { while (cur) { stack.push(cur); cur cur.left; } cur stack.pop(); result.push(cur.val); cur cur.right; } return result; };这段代码的关键在于理解cur的指向变化先一路向左走到底把所有左孩子压栈弹出一个节点输出后再转向它的右子树重复上面的过程。整个过程中stack保存的是还没被访问且需要等左子树处理完才能访问的祖先节点。如果理解不了我建议拿上面那棵树手动模拟一遍其实就是在模拟递归中保存现场、恢复现场的动作。3.4 后序遍历的前序变体反转技巧后序迭代如果用正统写法会非常繁琐因为它需要判断右子树是否处理完。一个取巧但很稳定的方案是仿照前序遍历但入栈顺序改成先压left再压right这样弹出的顺序是根、右、左最后把结果数组reverse一下得到左、右、根正好是后序遍历。const postorderTraversal (root) { if (!root) return []; const stack [root]; const result []; while (stack.length) { const node stack.pop(); result.push(node.val); if (node.left) stack.push(node.left); if (node.right) stack.push(node.right); } return result.reverse(); };这个技巧的好处是代码量少不容易写错。缺点是需要额外一次reverse的循环不过对时间复杂度影响不大O(n)的遍历成本是逃不掉的。三种迭代的对比总结一下遍历顺序核心思路栈的用法易错点前序根先入栈弹出就输出先压右再压左入栈顺序写反中序一路向左压栈弹出后转向右指针cur配合栈cur的更新逻辑混乱后序前序变体反转先压左再压右忘记reverse提示如果面试时只需要写一种迭代遍历优先选前序它代码最简单后序用反转技巧可以在五分钟内搞定。4. BFS层序遍历队列里装着的层次感4.1 为什么BFS天然配队列BFS广度优先搜索的目标是一层一层地扫描。想象一下用吸管喝分层饮料你得从最上面一层开始喝完一层再喝下一层。队列的FIFO先进先出特性正好呼应这个顺序先把根节点入队然后只从队头取出节点处理同时把它的左右子节点按顺序放到队尾下一轮再按这个顺序处理。4.2 基础版BFS实现const bfs (root) { if (!root) return []; const queue [root]; const result []; while (queue.length) { const node queue.shift(); result.push(node.val); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } return result; };用之前那棵树跑一遍结果就是1, 2, 3, 4, 5。你可以看到它不像DFS那样先深入左子树而是把同一层的节点全部处理完才进入下一层。这就是BFS和DFS最本质的区别BFS逐层推进DFS沿分支深入。4.3 分层BFS记录当前层节点数很多业务问题不仅需要知道遍历顺序还要求按层输出比如LeetCode的102题。这时需要用一个技巧在进入新一层之前先记录当前队列的长度levelSize这个长度就是该层的节点数。然后做一个for循环只弹出levelSize个节点这些节点必然都属于同一层。const levelOrder (root) { if (!root) return []; const queue [root]; const result []; while (queue.length) { const levelSize queue.length; const level []; for (let i 0; i levelSize; i) { const node queue.shift(); level.push(node.val); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } result.push(level); } return result; };这里的常见坑是没有提前记录levelSize而是在for循环里直接判断i queue.length。这样一来循环过程中push进去的下一层节点会被当成当前层节点一起弹出分层就乱了。我踩过一次这个坑输出结果全是乱的检查了半天才发现是判断条件用了动态的queue.length。4.4 别让shift毁了性能用索引模拟队列JavaScript数组的shift()方法会把所有剩余元素往前挪时间复杂度是O(n)。如果树的节点特别多比如上万级每次shift都触发一次整体迁移性能会很难看。一个高效替代方案是用索引指针模拟队头const bfsWithIndex (root) { if (!root) return []; const queue [root]; const result []; let head 0; while (head queue.length) { const node queue[head]; result.push(node.val); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } return result; };用head指针标记当前取到哪个位置每次递增即可元素不再挪动。这个写法在很多处理大量数据的前端场景里很实用比如大数据量的树形结构做BFS过滤。提示实际业务里除非树特别深或特别宽shift和索引模拟的差异不大。但在LeetCode或者需要处理百万级节点的场景用索引模拟队列会稳很多。5. 实战应用从LeetCode到真实业务场景5.1 求二叉树的最大深度DFS的经典变体有一道高频题是求二叉树最大深度也就是从根节点到最远叶子节点的路径长度。这个用后序DFS写起来非常优雅const maxDepth (root) { if (!root) return 0; return Math.max(maxDepth(root.left), maxDepth(root.right)) 1; };原因很简单当前节点的深度等于左右子树较大的深度再加1。递归到这里其实是标准的后序思想先拿到左子树的深度再拿右子树的深度最后处理当前节点。求最小深度时要注意一个陷阱如果某侧子树为空不能直接取Math.min因为空子树深度是0会把结果错误地变成1。需要做特殊判断这也是面试里容易踩的细节。5.2 对称二叉树的判断左右子树镜像对比判断一棵二叉树是否对称核心是递归对比左子树的left和右子树的right、以及左子树的right和右子树的left。这也是DFS的一个变体但要注意两个子树同时为空才是true一个为空一个不为空就是false。const isSymmetric (root) { const check (left, right) { if (!left !right) return true; if (!left || !right) return false; return left.val right.val check(left.left, right.right) check(left.right, right.left); }; return check(root.left, root.right); };这个题的题眼是对称比较是从根节点开始的左右交叉不是简单的左右子树相同。很多人一开始写成比较left.left和right.left那就变成判断两棵子树是否完全相等了概念搞混。5.3 树形菜单查找节点DFS和BFS哪个更合适在实际前端业务里我们的数据结构通常不是严格的二叉树而是多叉树每个节点可以有多个children但遍历思想完全一样。比如一个后台管理系统的菜单树需要根据id找到某个菜单项并高亮它。DFS的递归写法const findNodeDFS (menu, targetId) { for (const item of menu) { if (item.id targetId) return item; if (item.children) { const found findNodeDFS(item.children, targetId); if (found) return found; } } return null; };BFS的迭代写法const findNodeBFS (menu, targetId) { const queue [...menu]; while (queue.length) { const item queue.shift(); if (item.id targetId) return item; if (item.children) queue.push(...item.children); } return null; };两者的选择取决于场景。如果菜单很深但目标节点大概率在浅层BFS更快因为它是逐层扫描。如果菜单结构比较扁平DFS的递归写法更直观。另外如果树的深度非常大比如几千层递归DFS有栈溢出风险用BFS迭代更安全。这些分析在面试时说出来比单纯背代码有用得多。5.4 前端组件树的递归渲染React或Vue里渲染树形组件本质上就是DFS前序的应用。父组件render一个子组件子组件里又调用自身去渲染children这不就是前序的根 - left - right吗我早期开发目录树组件时就是靠理解DFS来写递归模板的const TreeNode ({ node }) ( div {node.name} {node.children node.children.map(child TreeNode key{child.id} node{child} /)} /div );想明白这一点后再遇到多层级嵌套的评论列表、测试用例的步骤树、权限菜单处理起来就顺手多了。6. 为什么你写二叉树程序总是报运行时错误排查经验分享6.1 最常见错误在null节点上访问属性你在控制台看到的报错通常是这样的TypeError: Cannot read properties of null (reading left)根因是代码在某个为null的节点上调用了.left或.val。最常见的发生位置有两类一是在递归函数里没写空判断或空判断写在了使用节点属性之后二是在迭代写法里把null节点压进了栈或队列。比如前序遍历迭代中如果不用if (node.right)判断而是直接stack.push(node.right)那么当一个节点的右孩子不存在时null就被压进栈等到弹出时就会报错。排查这类问题的思路很简单在while或递归函数开头打印当前node看看是哪一步把null推进来的。或者更直接一点在入栈、入队前统一加一个判断if (node.left) stack.push(node.left)。6.2 无限递归导致的栈溢出报错信息是Maximum call stack size exceeded。大部分情况是递归函数的终止条件没写好。比如你把if (!root) return写成了if (!root.left) return那么当root本身为null时函数在出口处访问root.left直接抛错如果树退化成链状递归深度过大也一样爆栈。解决办法是出口条件只判断当前节点是否为null不要在出口里去访问节点的子属性。如果你用的是迭代写法就没有递归栈溢出的问题这也是很多生产环境代码倾向于迭代遍历的原因之一。6.3 顺序错乱输出结果和预期遍历顺序不一致这类问题不报错但结果不对。比如前序迭代先压了left再压right输出的顺序会变成根右左。排查方法很土但有效找一个只有三个节点的标准小树手动在纸上模拟一遍入栈和出栈的过程对比代码每一步实际弹出的节点是哪个。我在带新人的时候发现一个规律大部分遍历顺序搞错的人都是因为把入栈顺序和输出顺序搞混了。记住一句话栈是先进后出队列是先进先出。DFS用栈BFS用队列这两个工具选对了问题解决一半。6.4 我的调试技巧打印缩进轨迹递归函数里打印缩进是我最喜欢的调试方式。原理很简单每次进入递归时根据当前深度打印一个带缩进的节点值退出时再打印一个返回。这样能在控制台里直观看到完整的递归调用过程const debugPreorder (root, depth 0) { if (!root) { console.log( .repeat(depth) null); return; } console.log( .repeat(depth) root.val); debugPreorder(root.left, depth 1); debugPreorder(root.right, depth 1); };输出效果类似这样1 2 4 null null 5 null null 3 null null看到这个递归到底是怎么走的、哪一步返回、哪一步为空一目了然。这个方法我强烈推荐给初学者比断点调试直观多了。6.5 边界测试用例空树、单节点、链状退化树写完一个遍历算法后至少用下面几种输入测试一遍空树root null函数应该直接返回空数组不报错。单节点树只有一个根节点所有遍历都应该输出这个节点。链状退化树每个节点只有左孩子或只有右孩子。这能暴露递归深度问题和迭代写法中cur指针的更新错误。完全二叉树左右子树都完整用于验证遍历顺序的正确性。这几个用例覆盖了绝大多数常见边界情况。我见过太多人在LeetCode上提交代码通过但在本地跑一个空树就直接崩掉的案例。多测几种边界比刷十道题都管用。最后再说说我个人的体会。DFS和BFS从来不是复杂到需要死记硬背的算法它们的本质就藏在栈和队列这两个基础数据结构里DFS顺着一条路探索到底BFS一层一层铺开。搞懂了这个二叉树的题目基本就通了。我建议拿到一个新题时不要急着敲代码先在纸上画一棵小树自己用栈或队列走一遍遍历顺序再动手写实现。这样练上十道题你就能形成肌肉记忆遇到任何树形数据都能自然说出这里该用DFS还是BFS。