Table of Contents
题目
分析
从这道题开始，我进入了一个之前没怎么接触的领域：二叉树。
先从本题开始，讲述一些基本的概念。
二叉树
二叉树是一种特殊的树，每个节点最多有两个子节点。它是一种非线性数据结构，代表“祖先”与“后代”之间的派生关系，体现了“一分为二”的分治逻辑。与链表类似，二叉树的基本单元是节点，每个节点包含值、左子节点引用和右子节点引用。
/* 二叉树节点结构体 */
struct TreeNode {
int val; // 节点值
TreeNode *left; // 左子节点指针
TreeNode *right; // 右子节点指针
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};在二叉树中，除叶节点外，其他所有节点都包含子节点和非空子树。
常用术语
- 根节点（root node）：位于二叉树顶层的节点，没有父节点。
- 叶节点（leaf node）：没有子节点的节点，其两个指针均指向 None 。
- 边（edge）：连接两个节点的线段，即节点引用（指针）。
- 节点所在的层（level）：从顶至底递增，根节点所在层为 1 。
- 节点的度（degree）：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2 。
- 二叉树的高度（height）：从根节点到最远叶节点所经过的边的数量。
- 节点的深度（depth）：从根节点到该节点所经过的边的数量。
- 节点的高度（height）：从距离该节点最远的叶节点到该节点所经过的边的数量。
完美二叉树、平衡二叉树、完全二叉树
完美二叉树（Perfect Binary Tree）
完美二叉树（perfect binary tree）所有层的节点都被完全填满。在完美二叉树中，叶节点的度为0，其余所有节点的度都为2；若树的高度为h，则节点总数为\(2^{h+1}-1\)，呈现标准的指数级关系，反映了自然界中常见的细胞分裂现象。
flowchart TD
A[1]-->B[2]
A-->C[3]
B-->D[4]
B-->E[5]
C-->F[6]
C-->G[7]
D-->H[8]
D-->I[9]
E-->J[10]
E-->K[11]
F-->L[12]
F-->M[13]
G-->N[14]
G-->O[15]
平衡二叉树（Balanced Binary Tree）
平衡二叉树（balanced binary tree）又叫完全二叉树（complete binary tree），只有最底层的节点未被填满，且最底层节点尽量靠左填充。请注意，完美二叉树也是一棵完全二叉树。
平衡二叉树的每个节点的左子树和右子树的高度差不超过1。
flowchart TD
A[1]-->B[2]
A-->C[3]
B-->D[4]
B-->E[5]
C-->F[6]
C-->G[7]
D-->H[8]
D-->I[9]
E-->J[10]
E-->K[11]
F-->L[12]
完全二叉树（Complete Binary Tree）
完全二叉树（complete binary tree）又叫完满二叉树。除了叶节点之外，其余所有节点都有两个子节点。
flowchart TD
A[1]-->B[2]
A-->C[3]
B-->D[4]
B-->E[5]
E-->F[6]
E-->G[7]
二叉树的命名很混乱。我这里采用的是Hello 算法中的命名方式。
本题练习的是如何求二叉树的高度。
由于没有约定二叉树的类型，所以只能用“笨”办法：分别找左子树和右子树的高度，取较大值。根据题意，0 0表示空树，所以遇到0的时候就可以返回0（没有高度）。同时，最终深度要加1，因为根节点的高度是1。
int maxDepth(const vector<Node>& tree, int root)
{
if (root == 0)
{
return 0;
}
int leftDepth = maxDepth(tree, tree[root].left);
int rightDepth = maxDepth(tree, tree[root].right);
return max(leftDepth, rightDepth) + 1;
}答案
思考
二叉树很重要！