当前位置：首页 > news >正文

吃透二叉树与递归！60分钟掌握树结构核心+解题思路

news 2026/6/12 1:02:16

一、为什么你学不会二叉树？

你是不是也觉得：

递归代码一看就懵，自己写总漏退出条件？
二叉树遍历记不住，前序、中序、后序傻傻分不清？
明明懂概念，一到实战就卡壳，不知道怎么落地？

今天这篇文章，我会用最通俗的语言、可直接运行的代码，带你从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：确定退出条件

n=1时，只有1种爬法（直接爬1步）
n=2时，有2种爬法（1+1 或 2）

步骤3：完整可运行代码

// 爬楼梯递归实现functionclimbStairs(n){// 退出条件：必须清晰，否则爆栈if(n===1)return1;if(n===2)return2;// 递归公式：拆解成小问题returnclimbStairs(n-1)+climbStairs(n-2);}// 测试：爬5阶楼梯，预期结果8console.log(climbStairs(5));// 输出8

2.3 踩坑提醒⚠️

递归一定要写退出条件！否则会无限调用，导致栈内存溢出（爆栈）
不要死记递归代码，要记“拆解问题+找公式+退出条件”的思路

三、二叉树：从定义到落地（JS版）

理解了递归，我们来看二叉树——它本身就是递归定义的结构。

3.1 二叉树的核心定义

可以是空树（没有任何节点）
非空树必须有：根节点 + 左子树 + 右子树（左右子树也是二叉树）
左右子树位置严格固定，不能交换！

3.2 JS如何表示二叉树？

用对象模拟二叉树节点，包含3部分：数据域、左子节点引用、右子节点引用：

// 定义二叉树节点functionTreeNode(val){this.val=val;// 数据域this.left=this.right=null;// 左右子节点引用（初始为空）}// 构建一棵完整的二叉树示例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 → G

4.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 → G

4.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 → A

4.2 迭代遍历：层序遍历（按层找）

递归用栈，层序遍历用队列，按层次从根到叶子遍历：

functionlevelorder(root){constqueue=[];// 队列存节点constresult=[];// 存遍历结果// 空树直接返回if(!root)returnresult;queue.push(root);// 根节点入队while(queue.length){constnode=queue.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']