[二叉树 binary tree] 是一种非线性数据结构，代表着祖先与后代之间的派生关系，体现着” 一分为二 “的分治逻辑。
二叉树的基本单元是节点，每个节点有：** 值、[左子节点 left-child node]引用、[右子节点 right-child node]** 引用。
class TreeNode {
int val;
TreeNode? left;
TreeNode? right;
TreeNode(int x) => val = x;
}
在二叉树中，除叶节点外，其他所有节点都包含子节点和非空子树(子节点及其以下节点形成的树)。
二叉树的常见术语#
- [根节点 root node]: 顶层节点，没有父节点。
- [叶节点 leaf node]: 没有子节点的节点。
- [边 edge]: 连接两个节点的线段，即节点引用（指针）。
- 节点所在的 [层 level]: 从顶至底递增，根节点所在层为 1。
- 节点的 [度 degree]: 节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2。
- 二叉树的 [高度 height]: 从根节点到最远叶节点所经过的边的数量。
- 节点的 [深度 depth]: 从根节点到该节点所经过的边的数量。
- 节点的 [高度 height]: 从最远叶节点到该节点所经过的边的数量。
💡 请注意，通常将 “高度” 和 “深度” 定义为 “走过边的数量”。
常见二叉树类型#
1. [完美 (满) 二叉树 perfect binary tree]#
除了最底层外，其余所有层的节点都被完全填满。
2. [完全二叉树 complete binary tree]#
只有最底层的节点未被填满，且最底层节点尽量靠左填充。
3. [完满二叉树 full binary tree]#
除了叶节点之外，其余所有节点都有两个子节点。
4. [平衡二叉树 balanced binary tree]#
任意节点的左子树和右子树的高度之差的绝对值不过超过 1。
二叉树遍历#
[层序遍历 level-order traversal]#
[层序遍历 level-order traversal] 从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。
层序遍历本质上属于 [广度优先遍历 breadth-first traversal]，体现了” 一圈一圈向外扩展 “的逐层遍历方式。
广度优先遍历通常借助” 队列” 来实现。
/* 层序遍历 */
List<int> LevelOrder(TreeNode root) {
// 初始化队列，加入根节点
Queue<TreeNode> queue = new();
queue.Enqueue(root);
// 初始化一个列表，用于保存遍历序列
List<int> list = new();
while (queue.Count != 0) {
TreeNode node = queue.Dequeue(); // 队列出队
list.Add(node.val); // 保存节点值
if (node.left != null)
queue.Enqueue(node.left); // 左子节点入队
if (node.right != null)
queue.Enqueue(node.right); // 右子节点入队
}
return list;
}
前序、中序、后序遍历#
前序、中序、后序遍历都属于 [深度优先遍历 depth-first traversal]，它体现了一种”先走到头，再回溯继续“的遍历方式。
深度优先遍历就像是绕着整个二叉树的外围” 走 “一圈，在每个节点都会遇到三个位置，分别对应前序遍历、中序遍历和后续遍历。
深度优先遍历通常基于递归实现。
/* **前序**遍历 */
void PreOrder(TreeNode? root) {
if (root == null) return;
// 访问优先级：**根**节点 -> **左**子树 -> **右**子树
list.Add(root.val);
PreOrder(root.left);
PreOrder(root.right);
}
/* **中序**遍历 */
void InOrder(TreeNode? root) {
if (root == null) return;
// 访问优先级：**左**子树 -> **根**节点 -> **右**子树
InOrder(root.left);
list.Add(root.val);
InOrder(root.right);
}
/* **后序**遍历 */
void PostOrder(TreeNode? root) {
if (root == null) return;
// 访问优先级：**左**子树 -> **右**子树 -> **根**节点
PostOrder(root.left);
PostOrder(root.right);
list.Add(root.val);
}
记忆口诀：
前序：根左右，中序：左根右，后序：左右根。