二叉树的递归遍历代码我大学时就能背前序中序后序一字不差。但第一次在面试现场让手写非递归版中序的时候我卡了十分钟没写出来。从那天起我才意识到会背递归代码和真正理解遍历是两码事。这篇文章想讲清楚JavaScript里二叉树遍历的那些“根底”。前序、中序、后序是二叉树家族里最基础也是最高频的三个题目LeetCode上几乎每一道二叉树题都会用到其中某一种而围绕它们演变出来的迭代写法、序列化、重建二叉树、Morris遍历又总能在面试和工程里反复出现。我会从怎么用JS把一棵树建出来开始讲到递归版三序遍历再到面试必问的迭代版三序遍历最后延伸一点重建二叉树和O(1)空间的Morris遍历。适合正在刷题的前端开发、准备面试的校招生以及任何想把二叉树遍历从“背代码”变成“真理解”的人。1. 先把树搭起来JS里的节点定义与LeetCode输入格式很多人一上来就写遍历结果卡在第一步树从哪来这个问题在本地IDE里写Demo时特别常见。LeetCode给你的是一个已经构建好的root节点但你自己练习时得手搓一棵树。所以我先讲怎么用JS把一棵二叉树老老实实建出来。1.1 节点类定义二叉树在代码里的最小单元是节点。JS里最常规的定义是class TreeNode { constructor(val 0, left null, right null) { this.val val; this.left left; this.right right; } }一个节点有三个字段自己的值val、左孩子left、右孩子right。没有孩子就存null。整棵树就是这样一个节点一个节点通过指针串起来的链式结构和链表非常像区别只是链表只有一个next二叉树有两个方向。我看到不少初学者纠结到底用class还是function都行但面试时class写法更常见也更容易读。手动构建一棵树的姿势是这样的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); root.right.right new TreeNode(6);这棵树的形状是1 / \ 2 3 / \ \ 4 5 6后面讲三种遍历的时候我会反复拿这棵树举例建议你脑子里先存下这个结构。1.2 LeetCode风格数组输入怎么转成树LeetCode上二叉树的输入往往给你一个层序数组比如[1, 2, 3, null, 5]意思是根节点值是1它左孩子是2右孩子是32的左孩子是null2的右孩子是5。这种格式的底层逻辑是“按层摆放”数组中第i个节点的左孩子在2 * i 1位置右孩子在2 * i 2位置。你可以用下面这个队列方法把数组转成一棵真正的二叉树function buildTreeFromArray(arr) { if (!arr || arr.length 0 || arr[0] null) return null; const root new TreeNode(arr[0]); const queue [root]; let i 1; while (i arr.length) { const node queue.shift(); if (arr[i] ! null) { node.left new TreeNode(arr[i]); queue.push(node.left); } i; if (i arr.length arr[i] ! null) { node.right new TreeNode(arr[i]); queue.push(node.right); } i; } return root; }这里有个细节值得注意为什么用队列而不是简单for循环因为层序数组里可能出现null节点null节点是没有孩子的如果直接用下标公式硬挂就会把一些本该挂到其它节点下面的子节点丢失。队列的做法是只有扫描到非空节点才放入队列然后每弹出一个节点就按顺序从数组里取接下来的两个值做它的左右孩子。这样能保证数组的“层序顺序”和树的实际结构一一对应。构造好树之后所有遍历代码都从这个root出发这才是完整的练习链路。2. 递归序才是理解三种遍历的核心别靠背递归版遍历的代码短得惊人前序三行中序三行后序三行。但很多人背下来之后换个题目就懵了。原因在于他们不知道这三行代码为什么在“那个位置”打印。我建议你彻底丢掉“前序就是根左右”这种口诀改成理解“递归序”。2.1 每个节点其实会被“访问”三次递归遍历二叉树的本质是对每个节点都先去处理它的左子树再处理右子树。但你别忘了函数在进入左子树之前要“路过”当前节点一次从左子树回来时要“路过”一次从右子树回来时还要“路过”一次。也就是说每个节点在递归过程中会被碰到三次。这个“碰到三次”就是递归序。在三次碰到的时候分别打印就得到了三种遍历第一次碰到就打印前序先根第二次碰到再打印中序左根右第三次碰到最后打印后序左右根拿上面那棵树完整跑一遍递归序过程是1第一次进入2 → 进入4 → 4没孩子三次都在4身上 → 回到2 → 2第二次 → 进入5 → 5三次 → 回到2 → 2第三次 → 回到1 → 1第二次 → 进入3 → 右边进入6 → 6三次 → 回到3 → 3第三次 → 回到1 → 1第三次。如果在“第一次碰到”打印结果是1、2、4、5、3、6。如果在“第二次碰到”打印结果是4、2、5、1、3、6。如果在“第三次碰到”打印结果是4、5、2、6、3、1。这三条序列和前面手动推的结果完全一致。理解了递归序之后你根本不用背代码只要记住“第几次”就行。2.2 递归版代码与复杂度// 前序遍历 function preorderTraversal(root) { const result []; function dfs(node) { if (!node) return; result.push(node.val); // 第一次碰到 dfs(node.left); dfs(node.right); } dfs(root); return result; } // 中序遍历 function inorderTraversal(root) { const result []; function dfs(node) { if (!node) return; dfs(node.left); result.push(node.val); // 第二次碰到 dfs(node.right); } dfs(root); return result; } // 后序遍历 function postorderTraversal(root) { const result []; function dfs(node) { if (!node) return; dfs(node.left); dfs(node.right); result.push(node.val); // 第三次碰到 } dfs(root); return result; }时间和空间复杂度需要说清楚。时间上每个节点都会被访问常数次所以时间复杂度是O(n)n是节点数。空间上递归调用用的是系统栈栈的深度取决于树的高度h均衡二叉树是O(log n)但遇到极端情况比如一棵退化成链表的树递归深度就是n空间复杂度O(n)。这也是为什么后面要写迭代版——很多面试官会追问“递归有栈溢出风险你怎么改”。2.3 根的位置决定了遍历名字前序的第一个元素一定是根后序的最后一个元素一定是根中序根在中间——这句话不是废话它是后面“重建二叉树”的理论基础。你能从一次遍历结果里拿到根的信息但这三种遍历各自携带的信息量不同前序和后序告诉你“谁在最上层”中序告诉你“根的左边全是左子树、右边全是右子树”。它们组合起来才能唯一定位一棵树。这个点我在第4节展开。3. 迭代版遍历自己维护栈不只是为了面试递归用的是系统栈迭代版就是自己压栈模拟递归过程。说实话工程里直接写递归就够了但面试官问迭代版至少有三个动机考察你对递归栈的理解、考察你处理边界条件的能力、考察极端情况下避免爆栈的工程意识。这一节我按“最容易理解”的顺序来写而不是按“前中后”的顺序写因为前序是迭代版的引子理解了前序后序其实是一行反转的事。3.1 前序迭代弹栈即打印先右后左入栈前序的顺序是“根、左、右”。用栈模拟时我们先把根压栈然后循环弹出一个节点打印接着把它的右孩子压栈再把左孩子压栈。为什么要先右后左因为栈是后进先出左孩子后进栈下一次循环就会先弹左孩子这样才符合“先左后右”的遍历顺序。function preorderTraversal(root) { const result []; if (!root) return result; const stack [root]; 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; }这个代码有一个新手必踩的坑把if (node.right)和if (node.left)的顺序写反了。写反之后你得到的是“根、右、左”序列不是前序。调试角度讲你拿一棵三层小树跑一遍就能看到差异。3.2 中序迭代一路向左弹栈转右中序迭代是三者里最需要动脑筋的也是面试出镜率最高的。核心思路是从当前节点出发一路把左孩子压栈直到没有左孩子然后弹栈打印之后把指针移到右孩子继续重复“一路向左”的过程。function inorderTraversal(root) { const result []; const stack []; let cur root; while (cur || stack.length) { while (cur) { stack.push(cur); cur cur.left; } const node stack.pop(); result.push(node.val); cur node.right; } return result; }我建议你在纸上把前面那棵树完整走一遍。第一次外层循环cur是1内层循环不断压栈压1、压2、压4然后cur变成null弹栈得到4打印cur指向4的右孩子null此时栈不为空继续外层循环cur还是null不进入内层弹栈得到2打印cur指向2的右孩子5下一轮压5然后弹出打印cur指向5的右孩子null再弹出1打印cur指向右孩子3继续压3再压6再弹6打3……最后结果就是[4, 2, 5, 1, 3, 6]。整个过程的核心是每当弹出一个节点它的左子树一定已经全部处理完了所以这个节点可以放心打印然后转到右子树去。3.3 后序迭代用前序变体加反转省心不烧脑后序迭代最容易写错很多教材给的双栈法又绕。这里分享一个我用了很多年的技巧先写出“根、右、左”的遍历然后整个结果反转就得到了“左、右、根”也就是后序。为什么能这样因为后序是“左右根”前序是“根左右”把前序的左右交换成“根右左”再反转顺序正好变成“左右根”。这不是巧合是序列本身的对偶关系。function postorderTraversal(root) { const result []; if (!root) return result; const stack [root]; 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()。这一招在面试里特别管用因为你不用去记忆复杂的状态转移逻辑也完全经得起推敲。三种迭代写法放在一起看各自的栈操作规律遍历方式栈的使用方式打印时机关键点前序弹栈即打印右先左后入栈弹栈时入栈顺序决定出栈顺序中序一路压左弹栈打印后转右弹栈时内层while负责把左链走完后序前序变体先左后右入栈最后统一反转反转省去复杂状态判断4. 用前序中序重建二叉树一道高频面试题的完整拆解理解了三种遍历之后有一个特别经典的进阶题给你前序和中序遍历的结果要求还原整棵二叉树。LeetCode第105题就是这个。这个题的价值在于它是“你知道遍历序列内部规律”的最直接证明。4.1 重建原理三个信息量各司其职前序的第一个元素一定是根节点这没有任何争议因为前序最先访问根。但在前序的剩余部分里哪些属于左子树、哪些属于右子树光靠前序序列分不出来。这时候中序序列就派上用场了在中序序列里找到根节点的位置根左边那一整段就是左子树的中序序列根右边那一整段就是右子树的中序序列。左右子树各有多少个节点这个数量是明确知道的于是回到前序序列就能精准切出左右子树各自的前序范围。递归往下做直到序列为空树就建完了。我拿前面的树举例。前序是[1, 2, 4, 5, 3, 6]中序是[4, 2, 5, 1, 3, 6]。前序第一个元素是1在中序里找到1在第3个位置从0开始所以左子树的中序是[4, 2, 5]长度为3右子树的中序是[3, 6]。在前序中根1后面的3个元素[2, 4, 5]是左子树前序再后面的[3, 6]是右子树前序。然后递归处理左子树和右子树就能还原出整棵树。4.2 代码实现与优化function buildTree(preorder, inorder) { if (!preorder.length || !inorder.length) return null; const rootVal preorder[0]; const root new TreeNode(rootVal); const midIndex inorder.indexOf(rootVal); root.left buildTree( preorder.slice(1, midIndex 1), inorder.slice(0, midIndex) ); root.right buildTree( preorder.slice(midIndex 1), inorder.slice(midIndex 1) ); return root; }这个版本用slice生成子数组可读性极好笔试面试时写这个完全没问题。但如果数据量很大每次slice都是O(n)的额外开销整体复杂度会退化到O(n²)。更优的做法是传索引下标只在原数组上切区间。function buildTree(preorder, inorder) { const map new Map(); inorder.forEach((val, index) map.set(val, index)); function build(preL, preR, inL, inR) { if (preL preR) return null; const rootVal preorder[preL]; const root new TreeNode(rootVal); const midIndex map.get(rootVal); const leftSize midIndex - inL; root.left build(preL 1, preL leftSize, inL, midIndex - 1); root.right build(preL leftSize 1, preR, midIndex 1, inR); return root; } return build(0, preorder.length - 1, 0, inorder.length - 1); }这里用Map提前记录每个值在中序里的位置省掉每次indexOf的线性查找。另外有个隐藏条件题目默认二叉树节点值不重复。如果值重复这种“用值定位根在中序中的位置”的做法就会失效必须靠额外的位置信息或者改成“按索引查找”。面试时主动提一句“这里假设节点值唯一”会让面试官觉得你考虑到了边界条件。4.3 后序中序重建思路完全一样如果给你的是后序和中序思路类似后序的最后一个元素是根在中序里找到根左边是左子树、右边是右子树。我会在代码注释里写一句后序倒着往前推先建右子树再建左子树因为后序序列从右往左看根之后先出现右子树的根。5. Morris遍历与遍历结果的实际用处到这里递归和迭代两种方式已经覆盖了前中后序。不过二叉树遍历还有一个比较“偏门”但很能体现功底的玩法Morris遍历。它的核心卖点是空间复杂度只有O(1)不使用栈也不使用递归而是靠临时修改树里的空指针来完成回溯。5.1 Morris中序遍历到底在干什么先看代码function morrisInorder(root) { const result []; let cur root; while (cur) { if (!cur.left) { result.push(cur.val); cur cur.right; } else { let predecessor cur.left; // 找到左子树的最右节点 while (predecessor.right predecessor.right ! cur) { predecessor predecessor.right; } if (!predecessor.right) { // 第一次到达建立线索指向当前节点 predecessor.right cur; cur cur.left; } else { // 第二次到达说明左子树已经处理完恢复树结构 predecessor.right null; result.push(cur.val); cur cur.right; } } } return result; }Morris遍历的关键在于“利用空闲的右指针”。当你站在某个节点cur上如果它有左子树就找到左子树的最右节点predecessor。这个最右节点原本的右指针是空的Morris办法是让它暂时指向cur。这样一来当你在左子树里一路走到最右就能顺着这个临时指针“爬”回cur而不用依赖系统栈或显式栈保存路径。等到第二次路过predecessor时发现它的right已经指向cur了就知道左子树处理完了这时把指针恢复成null打印cur然后去右子树。这个过程确实会临时改变树的结构但遍历结束时所有临时线索都被收回树会恢复原样。时间复杂度摊还下来仍然是O(n)但空间只有O(1)。前序和后序也都有Morris版本原理一致只是打印时机不同。实际工作中遇到特别深的树递归栈会溢出迭代栈也需要额外内存Morris可以作为一种无额外空间的备选方案面试里能主动写出Morris印象分会明显不一样。5.2 三种遍历结果在算法题和工程里的用途字符串序列化二叉树要存到数据库或传给别人通常用前序或后序遍历生成字符串配合null占位符再反序列化回树。LeetCode第297题就是标准例子。中序在前序/后序的辅助下才能完成反序列化或重建因为单独一种遍历无法唯一确定二叉树。BST性质的判定二叉搜索树的中序遍历结果严格递增。所以判断一棵树是不是BST直接中序遍历一遍看序列是否递增就行。这个技巧比递归比较每个节点的上下界更直观、更好记。表达式求值表达式(a b) * c可以表示成二叉树操作符在根节点左右子节点是操作数。前序得到前缀表达式中序得到中缀表达式后序得到后缀表达式。编译器里抽象语法树AST的处理思路和这套逻辑一脉相承。UI组件树的渲染前端组件树本身就是多叉树但原理相通。深度优先遍历前序常用于先渲染父组件再渲染子组件目录结构展示时前序对应“先展示文件夹再展示里面内容”后序则用于“先删除子文件再删除文件夹”这类场景。5.3 顺便聊聊层序遍历虽然标题是前中后序但层序遍历值得放在一起记。它用的是队列不是栈function levelOrder(root) { if (!root) return []; const result []; const queue [root]; 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因为队列长度会随着入队操作动态变化如果不提前固定一层的大小就没法区分哪些节点属于同一层。这个levelSize思维在“按层处理”的题里是通用套路。我练二叉树遍历的体会是不要只看不写。拿同一棵树分别用递归版、迭代版各跑一遍前中后序在纸上把每次进栈、出栈的节点记下来两三棵树之后你就能建立起对“递归序”的直觉。之后再遇到二叉树深度、最近公共祖先、路径总和这些题你会发现它们不过是遍历的变体换了个打印时机和处理逻辑而已。这种手感靠背题是背不出来的。