二叉树专题导读

为什么二叉树是算法的分水岭

链表是线性递推，数组是线性下标，二叉树第一次让"数据结构"出现了分叉：一个节点有两个后继，问题天然裂解成"左子树怎么办、右子树怎么办"。这个裂解恰恰是递归思维的完美训练场——绝大多数二叉树题的本质，是把一个全局问题拆成两个形状相同但规模更小的子问题。

树也是后续所有章节的地基：回溯的决策树、二叉搜索树的查找、堆的完全二叉树实现、甚至红黑树和 B+ 树（数据库索引的底层），全都建立在二叉树的概念之上。这一章慢一点、透一点，后面全是顺风局。

四种特殊形态的定义要抠准

二叉树本身定义简单：每个节点至多两个孩子的树。真正容易混淆的是四个"形容词"，定义边界必须一字不差：

两个最常踩的坑：

1. 完全二叉树的判断看"编号连续性"：按层编号，若中间出现空洞就不是。[1,2,3,_,5] 不是完全二叉树（4 号缺但 5 号在），[1,2,3,4,_] 是。
2. 二叉搜索树是"整棵左子树都小于根"，不是"左孩子小于根"。[5,1,6,3,7] 若只比父子会误判为 BST——3 在 6 的左子树里却在 5 的右子树一侧，违反全局约束。验证 BST 必须传上下界或用中序有序性。

Java 节点定义与两种存储

刷题用的标准节点定义（LeetCode 已内置，自己本地调试时需要手写）：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

树在内存里有两种存法：

链式存储：就是上面的节点定义，用引用串起来。刷题 99% 用它，插入删除灵活，缺点是只有指针没有下标，无法 O(1) 定位"第 i 个节点"。

数组存储（堆的存储方式）：按层序编号放进数组，编号 i 的节点：

• 左孩子：2i + 1，右孩子：2i + 2（0 起始下标）；
• 父节点：(i - 1) / 2。

        A(0)
       /    \
     B(1)    C(2)
     /  \
   D(3)  E(4)

数组: [A, B, C, D, E]
下标:  0  1  2  3  4     E 的下标 4 → 左孩子 9、右孩子 10，越界即无孩子

数组存储省掉所有指针开销，但要求数组形状尽量"满"——这正是完全二叉树的主场，PriorityQueue（堆）和 Arrays.sort 的底层都基于它。理解 2i+1 / 2i+2，堆的上浮下沉代码就不再神秘。

专题学习地图

二叉树题目数量庞大，但没有必要恐惧——按下面的主线走，每一步都是在前一步上加一点点东西：

二叉树
├── 第一层：遍历（一切的地基）
│    ├── 前中后序递归 / 迭代 / 统一迭代
│    └── 层序遍历 BFS（102 系）
├── 第二层：属性求值（遍历 + 返回值设计）
│    ├── 深度与高度：104 / 111 / 110
│    ├── 结构判断：101 对称 / 222 节点数
│    └── 路径类：112 路径总和 / 257 所有路径
├── 第三层：修改与构造
│    ├── 226 翻转 / 617 合并
│    ├── 105 前序+中序构造 / 106 中序+后序构造
│    └── 654 最大二叉树 / 108 有序数组转 BST
├── 第四层：二叉搜索树
│    ├── 700 搜索 / 98 验证 / 530 最小绝对差
│    ├── 701 插入 / 450 删除 / 669 修剪
│    └── 538 累加树（中序逆序）
└── 第五层：公共祖先
     ├── 236 普通二叉树的最近公共祖先
     └── 235 BST 的最近公共祖先（利用有序性剪枝）

• 第一层是地基：不会遍历，后面全部免谈。递归三要素 + 层序 BFS 模板要练到肌肉记忆。
• 第二层学"返回值设计"：求高度用后序（自底向上收集），求深度用前序（自顶向下传递），这是本层核心功法。
• 第三层学"分而治之"：构造类题目的套路高度一致——找根、切分左右区间、递归构造。
• 第四层吃透"有序性"：BST 的中序遍历天然有序，一半的 BST 题靠这一条性质解决。
• 第五层是综合：公共祖先的递归后序逻辑，是前四层所有技巧的集中演练。

学习方法建议

1. 先写递归三要素再动手：函数参数和返回值是什么、终止条件是什么、单层逻辑是什么。三句话说不出，代码写出来也是碰运气。
2. 树形结构一定要画图：递归调用栈在纸上画展开图，比在脑子里空转有效十倍。
3. 一个函数一个职责：求高度就只求高度，不要顺便做平衡判断，职责混在一起往往写出 O(n²) 的隐藏 bug。

LeetCode 大题单（分块）

题单虽长，但每个板块只引入一个新概念。按板块顺序推进，每个板块内先做加粗的经典题再做衍生题，两三周可以完整走一遍。

参考

• 代码随想录 · 二叉树专题