二叉树（Binary Tree）
📌 定义
二叉树是每个节点最多有两个子节点的树结构，通常称为左子节点和右子节点。
1
/ \
2 3
/ \ \
4 5 6
🎯 核心特点
- 每个节点最多2个子节点：左子节点和右子节点
- 递归结构：每个子树也是二叉树
- 层次结构：从根节点开始，逐层向下
- 有序性：左右子节点有区别
📚 二叉树分类
1. 满二叉树（Full Binary Tree）
每个节点要么是叶子节点，要么有两个子节点。
1
/ \
2 3
/ \ / \
4 5 6 7
2. 完全二叉树（Complete Binary Tree）
除最后一层外都是满的，最后一层从左到右连续。
1
/ \
2 3
/ \ /
4 5 6
特点：
- 堆就是完全二叉树
- 可以用数组高效存储
3. 平衡二叉树（Balanced Binary Tree）
任意节点的左右子树高度差不超过1。
4. 二叉搜索树（BST）
详见 二叉搜索树
💻 节点定义
Go
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}🔄 二叉树遍历
📊 遍历对比
| 遍历方式 | 访问顺序 | 应用场景 | 空间复杂度 |
|---|---|---|---|
| 前序 | 根-左-右 | 复制树、序列化 | O(h) |
| 中序 | 左-根-右 | BST有序输出 | O(h) |
| 后序 | 左-右-根 | 删除树、计算 | O(h) |
| 层序 | 逐层访问 | BFS、最短路径 | O(w) |
h 为树高，w 为树的最大宽度
🎯 基本操作
🎯 路径问题
🎯 构造问题
经典题目
遍历相关
- 二叉树的前序遍历 - LeetCode 144
- 二叉树的中序遍历 - LeetCode 94
- 二叉树的后序遍历 - LeetCode 145
- 二叉树的层序遍历 - LeetCode 102
- 二叉树的锯齿形层序遍历 - LeetCode 103
树的属性
- 二叉树的最大深度 - LeetCode 104
- 二叉树的最小深度 - LeetCode 111
- 平衡二叉树 - LeetCode 110
- 对称二叉树 - LeetCode 101
- 二叉树的直径 - LeetCode 543
路径问题
- 路径总和 - LeetCode 112
- 路径总和 II - LeetCode 113
- 二叉树中的最大路径和 - LeetCode 124
- 二叉树的所有路径 - LeetCode 257
修改树结构
构造问题
- 从前序与中序遍历序列构造二叉树 - LeetCode 105
- 从中序与后序遍历序列构造二叉树 - LeetCode 106
- 最大二叉树 - LeetCode 654
其他
- 二叉树的序列化与反序列化 - LeetCode 297
- 完全二叉树的节点个数 - LeetCode 222
- 二叉树的右视图 - LeetCode 199
⚙️ 时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 遍历 | O(n) | 访问每个节点一次 |
| 查找 | O(n) | 最坏情况需遍历所有节点 |
| 插入 | O(h) | h为树高 |
| 删除 | O(h) | h为树高 |
| 计算高度 | O(n) | 需访问所有节点 |
⚖️ 优缺点
优点
- ✅ 结构清晰，递归处理简单
- ✅ 适合表达层次关系
- ✅ 搜索、排序效率高（BST）
缺点
- ❌ 空间开销大（指针）
- ❌ 非平衡树性能差
- ❌ 删除操作复杂
🎨 应用场景
- 文件系统：目录结构
- 表达式树：编译器语法分析
- 决策树：机器学习
- DOM树：HTML/XML解析
- 数据库索引：B树、B+树