二叉树（Binary Tree）
定义
二叉树是每个节点最多有两个子节点（左子节点和右子节点）的树结构。它是大多数高级数据结构的基础，也是一种核心算法思维。
核心特性
基本结构
class TreeNode {
int val;
TreeNode left, right;
}
重要性
- 数据结构基础：红黑树、多叉树、二叉堆、图、字典树、并查集、线段树等高级数据结构均基于二叉树
- 算法思维：回溯、BFS、动态规划等穷举算法本质是将问题抽象为树结构
常见类型
| 类型 | 英文术语 | 特点 |
|---|---|---|
| 满二叉树 | Perfect Binary Tree | 每层节点全满，总节点数 = 2^h - 1（h为深度） |
| 完全二叉树 | Complete Binary Tree | 节点紧凑靠左排列，除最后一层外每层全满 |
| 二叉搜索树 | Binary Search Tree (BST) | 左子树所有节点值 < 当前节点值 < 右子树所有节点值 |
| 高度平衡二叉树 | Height-Balanced Binary Tree | 每个节点的左右子树高度差 ≤ 1，树高为 O(logN) |
| 自平衡二叉树 | Self-Balanced Binary Tree | 增删节点时自动调整结构保持平衡（如红黑树） |
注意中英文差异：中文「满二叉树」对应英文 Perfect Binary Tree；英文 Full Binary Tree 指所有节点要么无子节点、要么有两个子节点。
实现方式
- 链式存储：最常见的
TreeNode结构，含左右子节点指针 - 数组存储：完全二叉树/二叉堆等场景，利用索引规律（父节点 i，左子节点 2i+1，右子节点 2i+2）
- 哈希表（邻接表）：用键值对表示父子关系，等价于图的邻接表表示
- 递归树：基于函数调用栈生成的递归树结构
遍历方式
二叉树只有两种遍历方式：
| 遍历方式 | 本质 | 衍生算法 |
|---|---|---|
| 递归遍历（DFS） | 依赖函数调用栈，先左后右固定顺序 | DFS 算法、回溯算法 |
| 层序遍历（BFS） | 借助队列，一层一层遍历 | BFS 算法 |
递归遍历的三个关键位置
| 位置 | 执行时机 | 效果 |
|---|---|---|
| 前序位置 | 刚进入节点时 | 前序遍历 |
| 中序位置 | 左子树完成后，右子树前 | 中序遍历（BST 中序遍历有序） |
| 后序位置 | 左右子树都完成后 | 后序遍历 |