一、为什么你学不会二叉树你是不是也觉得递归代码一看就懵自己写总漏退出条件二叉树遍历记不住前序、中序、后序傻傻分不清明明懂概念一到实战就卡壳不知道怎么落地今天这篇文章我会用最通俗的语言、可直接运行的代码带你从0到1吃透二叉树与递归。学完你能搞定理解递归的核心逻辑再也不怕写递归代码掌握二叉树4种遍历方式前/中/后/层序能用JS实现二叉树的定义与遍历解决类似爬楼梯的递归问题二、先搞懂递归到底是什么递归是二叉树的灵魂先把递归掰明白二叉树就通了一半。2.1 递归的核心三要素递归不是“玄学”只要抓住3点写递归就像套公式自顶向下拆解问题把大问题拆成和原问题相似的小问题找到递归公式小问题的解能组合成大问题的解明确退出条件避免无限递归爆栈2.2 实战案例爬楼梯问题用经典的爬楼梯问题理解递归一看就会问题爬n阶楼梯每次只能爬1或2阶有多少种不同的爬法步骤1拆解问题找递归公式爬n阶的最后一步要么是从n-1阶爬1步要么是从n-2阶爬2步递归公式f(n) f(n-1) f(n-2)步骤2确定退出条件n1时只有1种爬法直接爬1步n2时有2种爬法11 或 2步骤3完整可运行代码// 爬楼梯递归实现functionclimbStairs(n){// 退出条件必须清晰否则爆栈if(n1)return1;if(n2)return2;// 递归公式拆解成小问题returnclimbStairs(n-1)climbStairs(n-2);}// 测试爬5阶楼梯预期结果8console.log(climbStairs(5));// 输出82.3 踩坑提醒⚠️递归一定要写退出条件否则会无限调用导致栈内存溢出爆栈不要死记递归代码要记“拆解问题找公式退出条件”的思路三、二叉树从定义到落地JS版理解了递归我们来看二叉树——它本身就是递归定义的结构。3.1 二叉树的核心定义可以是空树没有任何节点非空树必须有根节点 左子树 右子树左右子树也是二叉树左右子树位置严格固定不能交换3.2 JS如何表示二叉树用对象模拟二叉树节点包含3部分数据域、左子节点引用、右子节点引用// 定义二叉树节点functionTreeNode(val){this.valval;// 数据域this.leftthis.rightnull;// 左右子节点引用初始为空}// 构建一棵完整的二叉树示例consttree{val:A,// 根节点left:{val:B,left:{val:D,left:null,right:null},right:{val:E,left:null,right:null}},right:{val:C,left:{val:F,left:null,right:null},right:{val:G,left:null,right:null}}};3.3 二叉树的关键概念必记层次根节点是第1层子节点第2层依此类推高度叶子节点高度为1每向上一层1度节点有多少个子树比如叶子节点度为0叶子节点度为0的节点最后一层节点四、二叉树的4种遍历方式实战拉满遍历是二叉树最核心的操作分为递归遍历前/中/后序和迭代遍历层序全部给你写好可运行代码。4.1 递归遍历先左后右是关键递归遍历的核心逻辑先处理当前节点/先处理子节点顺序不同对应不同遍历方式。4.1.1 前序遍历根 → 左 → 右先访问根节点再遍历左子树最后遍历右子树functionpreorder(root){// 退出条件节点为空则返回if(!root)return;// 1. 先处理根节点console.log(当前遍历节点${root.val});// 2. 遍历左子树preorder(root.left);// 3. 遍历右子树preorder(root.right);}// 测试preorder(tree);// 输出A → B → D → E → C → F → G4.1.2 中序遍历左 → 根 → 右先遍历左子树再访问根节点最后遍历右子树functioninorder(root){if(!root)return;// 1. 遍历左子树inorder(root.left);// 2. 处理根节点console.log(当前遍历节点${root.val});// 3. 遍历右子树inorder(root.right);}// 测试inorder(tree);// 输出D → B → E → A → F → C → G4.1.3 后序遍历左 → 右 → 根先遍历左子树再遍历右子树最后访问根节点functionpostorder(root){if(!root)return;// 1. 遍历左子树postorder(root.left);// 2. 遍历右子树postorder(root.right);// 3. 处理根节点console.log(当前遍历节点${root.val});}// 测试postorder(tree);// 输出D → E → B → F → G → C → A4.2 迭代遍历层序遍历按层找递归用栈层序遍历用队列按层次从根到叶子遍历functionlevelorder(root){constqueue[];// 队列存节点constresult[];// 存遍历结果// 空树直接返回if(!root)returnresult;queue.push(root);// 根节点入队while(queue.length){constnodequeue.shift();// 出队先进先出result.push(node.val);// 记录当前节点// 左子节点入队if(node.left)queue.push(node.left);// 右子节点入队if(node.right)queue.push(node.right);}returnresult;}// 测试console.log(levelorder(tree));// 输出[A,B,C,D,E,F,G]4.3 踩坑提醒⚠️递归遍历记住“先左后右”区别只在处理根节点的时机层序遍历用队列shift/push别和栈搞混遍历前一定要判断节点是否为空避免访问null的属性五、总结核心知识点速记递归三要素拆解问题 递归公式 退出条件二叉树定义空树 或 根左子树右子树左右位置固定遍历方式前序根左右中序左根右后序左右根层序按层队列实现核心思想二叉树的所有操作本质都是基于遍历的变形
吃透二叉树与递归！60分钟掌握树结构核心+解题思路
发布时间：2026/6/12 0:52:31
一、为什么你学不会二叉树你是不是也觉得递归代码一看就懵自己写总漏退出条件二叉树遍历记不住前序、中序、后序傻傻分不清明明懂概念一到实战就卡壳不知道怎么落地今天这篇文章我会用最通俗的语言、可直接运行的代码带你从0到1吃透二叉树与递归。学完你能搞定理解递归的核心逻辑再也不怕写递归代码掌握二叉树4种遍历方式前/中/后/层序能用JS实现二叉树的定义与遍历解决类似爬楼梯的递归问题二、先搞懂递归到底是什么递归是二叉树的灵魂先把递归掰明白二叉树就通了一半。2.1 递归的核心三要素递归不是“玄学”只要抓住3点写递归就像套公式自顶向下拆解问题把大问题拆成和原问题相似的小问题找到递归公式小问题的解能组合成大问题的解明确退出条件避免无限递归爆栈2.2 实战案例爬楼梯问题用经典的爬楼梯问题理解递归一看就会问题爬n阶楼梯每次只能爬1或2阶有多少种不同的爬法步骤1拆解问题找递归公式爬n阶的最后一步要么是从n-1阶爬1步要么是从n-2阶爬2步递归公式f(n) f(n-1) f(n-2)步骤2确定退出条件n1时只有1种爬法直接爬1步n2时有2种爬法11 或 2步骤3完整可运行代码// 爬楼梯递归实现functionclimbStairs(n){// 退出条件必须清晰否则爆栈if(n1)return1;if(n2)return2;// 递归公式拆解成小问题returnclimbStairs(n-1)climbStairs(n-2);}// 测试爬5阶楼梯预期结果8console.log(climbStairs(5));// 输出82.3 踩坑提醒⚠️递归一定要写退出条件否则会无限调用导致栈内存溢出爆栈不要死记递归代码要记“拆解问题找公式退出条件”的思路三、二叉树从定义到落地JS版理解了递归我们来看二叉树——它本身就是递归定义的结构。3.1 二叉树的核心定义可以是空树没有任何节点非空树必须有根节点 左子树 右子树左右子树也是二叉树左右子树位置严格固定不能交换3.2 JS如何表示二叉树用对象模拟二叉树节点包含3部分数据域、左子节点引用、右子节点引用// 定义二叉树节点functionTreeNode(val){this.valval;// 数据域this.leftthis.rightnull;// 左右子节点引用初始为空}// 构建一棵完整的二叉树示例consttree{val:A,// 根节点left:{val:B,left:{val:D,left:null,right:null},right:{val:E,left:null,right:null}},right:{val:C,left:{val:F,left:null,right:null},right:{val:G,left:null,right:null}}};3.3 二叉树的关键概念必记层次根节点是第1层子节点第2层依此类推高度叶子节点高度为1每向上一层1度节点有多少个子树比如叶子节点度为0叶子节点度为0的节点最后一层节点四、二叉树的4种遍历方式实战拉满遍历是二叉树最核心的操作分为递归遍历前/中/后序和迭代遍历层序全部给你写好可运行代码。4.1 递归遍历先左后右是关键递归遍历的核心逻辑先处理当前节点/先处理子节点顺序不同对应不同遍历方式。4.1.1 前序遍历根 → 左 → 右先访问根节点再遍历左子树最后遍历右子树functionpreorder(root){// 退出条件节点为空则返回if(!root)return;// 1. 先处理根节点console.log(当前遍历节点${root.val});// 2. 遍历左子树preorder(root.left);// 3. 遍历右子树preorder(root.right);}// 测试preorder(tree);// 输出A → B → D → E → C → F → G4.1.2 中序遍历左 → 根 → 右先遍历左子树再访问根节点最后遍历右子树functioninorder(root){if(!root)return;// 1. 遍历左子树inorder(root.left);// 2. 处理根节点console.log(当前遍历节点${root.val});// 3. 遍历右子树inorder(root.right);}// 测试inorder(tree);// 输出D → B → E → A → F → C → G4.1.3 后序遍历左 → 右 → 根先遍历左子树再遍历右子树最后访问根节点functionpostorder(root){if(!root)return;// 1. 遍历左子树postorder(root.left);// 2. 遍历右子树postorder(root.right);// 3. 处理根节点console.log(当前遍历节点${root.val});}// 测试postorder(tree);// 输出D → E → B → F → G → C → A4.2 迭代遍历层序遍历按层找递归用栈层序遍历用队列按层次从根到叶子遍历functionlevelorder(root){constqueue[];// 队列存节点constresult[];// 存遍历结果// 空树直接返回if(!root)returnresult;queue.push(root);// 根节点入队while(queue.length){constnodequeue.shift();// 出队先进先出result.push(node.val);// 记录当前节点// 左子节点入队if(node.left)queue.push(node.left);// 右子节点入队if(node.right)queue.push(node.right);}returnresult;}// 测试console.log(levelorder(tree));// 输出[A,B,C,D,E,F,G]4.3 踩坑提醒⚠️递归遍历记住“先左后右”区别只在处理根节点的时机层序遍历用队列shift/push别和栈搞混遍历前一定要判断节点是否为空避免访问null的属性五、总结核心知识点速记递归三要素拆解问题 递归公式 退出条件二叉树定义空树 或 根左子树右子树左右位置固定遍历方式前序根左右中序左根右后序左右根层序按层队列实现核心思想二叉树的所有操作本质都是基于遍历的变形
机制与中断回调)
