二叉树

1. 二叉树简介

二叉树是一种层次型数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树是许多更复杂数据结构和算法的基础。

来源：README.md:186

2. 二叉树结构与术语

在LeetCode-Master仓库中，二叉树通常采用类似于以下结构来表示

关键术语

根节点：树的顶部节点
节点：包含数据和子节点引用的基本元素
叶节点 (Leaf)：没有子节点的节点
边：两个节点之间的连接
高度：从根节点到叶节点的最大边数
深度：从节点到根节点的边数

来源：README.md:186

3. 二叉树的类型

仓库中涵盖了几种特殊的二叉树类型

类型	描述	相关问题
完全二叉树	除最后一层外，每一层都被填满，最后一层从左到右填充	#222
平衡二叉树	左右子树的高度差至多为 1	#110
二叉搜索树 (BST)	左子树值 < 节点值 < 右子树值	#98, #700, #530, #701, #450
对称二叉树	树是自身的镜像	#101

来源：README.md:186-219

4. 二叉树遍历方法

遍历是访问二叉树中所有节点的过程。该仓库涵盖了四种主要的遍历方法。

4.1 递归遍历

三种经典的递归遍历顺序

来源：README.md:187

4.2 迭代遍历

迭代实现使用显式栈，而不是递归中使用的隐式调用栈。

来源：README.md:188

4.3 统一迭代方法

该仓库提出了一种统一的方法，使用单个模板迭代实现所有三种遍历方法。

来源：README.md:189

4.4 层序遍历

也称为广度优先遍历，它逐层处理树。

来源：README.md:190

5. 常见操作和问题模式

5.1 树的反转

反转二叉树 (LeetCode #226) 是一个经典问题，涉及交换每个节点的左右子节点。

来源：README.md:191

5.2 对称性验证

通过比较左右子树是否互为镜像来检查树是否对称 (LeetCode #101)。

来源：README.md:193

5.3 深度计算

查找二叉树的最大深度 (LeetCode #104) 和最小深度 (LeetCode #111)。

来源：README.md:194-195

5.4 节点计数

使用优化方法计算完全二叉树中的节点数 (LeetCode #222)。

来源：README.md:196

5.5 路径查找

识别所有路径 (LeetCode #257) 或具有特定属性的路径 (LeetCode #112)。

来源：README.md:198, 202

6. 二叉搜索树 (BST)

二叉搜索树是节点遵循排序属性的特殊二叉树。

6.1 BST 操作

操作	描述	问题参考
搜索	高效定位一个值	#700
验证	验证树是否为有效的BST	#98
插入	添加新值并保持BST属性	#701
删除	删除值并保持BST属性	#450
最小差值	查找任意两个节点之间的最小差值	#530
查找众数	查找最常出现的值	#501

来源：README.md:207-218

6.2 BST 转换

该仓库涵盖了几种BST转换技术

将排序数组转换为BST (#108)
将BST转换为累加树 (#538)

来源：README.md:217-218

7. 最近公共祖先 (LCA)

查找两个节点的最近公共祖先是一个经常出现的问题模式。

涵盖了两种不同的实现

普通二叉树中的LCA (#236)
二叉搜索树的优化LCA (#235)

来源：README.md:211-213

8. 解题方法

解决二叉树问题时，该仓库推荐以下方法

理解问题需要自顶向下还是自底向上遍历
确定合适的遍历方法（前序、中序、后序、层序）
决定采用递归还是迭代实现
对于递归解决方案，清晰定义递归函数的
- 基本情况
- 返回值
- 状态参数

来源：README.md:219

9. 综合问题集

该仓库提供了一系列结构化问题，以培养二叉树技能

问题类别	代表性问题
基本遍历	递归/迭代/统一/层序遍历
树的属性	反转 (#226), 对称性 (#101), 深度 (#104, #111)
节点操作	节点计数 (#222), 路径查找 (#257, #112, #113)
树的构建	从遍历序列构建 (#106), 最大二叉树 (#654)
树的合并	合并两棵树 (#617)
BST 操作	搜索 (#700), 验证 (#98), 插入 (#701), 删除 (#450)
高级主题	LCA (#236, #235), BST转换 (#108, #538)