将森林转换为对应的二叉树，若在二叉树中，结点 u 是结点 v 的父结点的父结点，则在原来的森林中，u 和 v 可能具有的关系是( )。
I. 父子关系
II. 兄弟关系
III. u 的父结点与 v 的父结点是兄弟关系
目标
- 独立辨析树与森林中的核心概念、结构性质与遍历关系；
- 对选择题写出排除干扰项的依据，而不只记忆答案字母；
- 对源文档提供的综合题完成推导、算法设计或复杂度分析。
前置知识
建议先阅读第 4 章对应教材，再开始本组练习。
环境、输入与预期输出
- 环境：任意现代浏览器；综合题建议准备纸笔或本地编辑器。
- 输入：20 道四选一选择题，5 道综合题。
- 预期输出：一份独立作答记录，以及每道错题或综合题的完整推理过程。
作答方法
- 选择题先独立判断并记录依据，再点击“提交答案”；
- 提交后核对正确答案和解析，做错的题使用“重新作答”；
- 综合题先完成推导、伪代码或代码，再展开参考答案逐项核对；
- 对重复出现的真题，说明它在不同知识主题下分别考查了什么。
选择题
答题进度已答 0/20正确 0
难度★★★考点树与森林、树的度、叶结点、结点计数
在一棵度数为 4 的树 T 中，若有 20 个度为 4 的结点，10 个度为 3 的结点，1 个度为 2 的结点，10 个度为 1 的结点，则树 T 的叶结点个数是( )。
难度★★★★考点树与森林、森林、二叉树、孩子兄弟法、叶子
将森林 F 转换为对应的二叉树 T，F 中叶子的个数等于( )。
难度★★考点树与森林、森林、树性质、结点边数关系
若森林 F 有 15 条边、25 个结点，则 F 包含树的个数是( )。
难度★★★★考点森林与二叉树的转换、由遍历序列构造二叉树、树与森林、森林、二叉树转换、先序中序
某森林 F 对应的二叉树为 T , 若 T 的先序遍历序列是 a, b, d, c, e, g, f , 中序遍历序列是 b, d, a, e, g, c, f , 则 F 中树的棵数是( )。
难度★★★考点树与森林、三叉树、树高度、满 m 叉树
若三叉树 T 中有 244 个结点（叶结点的高度为 1），则 T 的高度至少是 ( )。
难度★★★★考点二叉树基础（性质+存储）、树与森林、森林转二叉树、孩子兄弟法、二叉树高度
森林 F 中有 5 颗树，其节点个数分别为 2、3、4、5、7，森林中树的次序可以任意，问 F 对应的二叉树最小高度为多少？
难度★★考点树与森林、树的性质、边数、分支数、结点数
一棵含 10 个结点的一般树（树根、叶子以及内部结点都任意），其分支数（即边的总条数）为( )。
难度★★★考点树与森林、树的性质、度数和、边数
一棵含 25 个结点的一般树，所有结点的度数之和为( )。
难度★★★考点树与森林、树的性质、度数和、度序列、结点数
一棵一般树中，含有 1 个度为 4 的结点、2 个度为 3 的结点、2 个度为 2 的结点，其余结点均为叶子（度为 0）。该树共有( )个结点。
难度★★★★考点树与森林、树的存储、双亲表示法、孩子表示法、孩子兄弟法
在树的三种典型存储方式（双亲表示法、孩子表示法、孩子兄弟法）中，查找指定结点的父结点的操作时间复杂度最优的是( )。
难度★★★考点树与森林、树的存储、双亲表示法、时间复杂度
用双亲表示法存储一棵含
难度★★★★考点树与森林、树的存储、孩子兄弟法、二叉链表
用孩子兄弟法存储一棵一般树（每个结点存两个指针 firstChild 和 nextSibling），下列说法错误的是( )。
难度★★★考点树与森林、树的转换、孩子兄弟法、二叉树
将下列一般树
的结构：根 有 3 个孩子 （按从左到右顺序）； 有 2 个孩子 （按从左到右顺序）； 是叶子； 有 1 个孩子 。
转换后二叉树
难度★★★★考点树与森林、树的转换、孩子兄弟法、结点数、根的右子树
用孩子兄弟法把一棵含 25 个结点的一般树
难度★★★★考点树与森林、森林、孩子兄弟法、二叉树转换、兄弟链
将下列森林
由 3 棵树组成（按从左到右顺序）：
：根 有 2 个孩子 ； ：根 是叶子； ：根 有 1 个孩子 。
转换后二叉树
难度★★★★考点树与森林、树的遍历、先根遍历、前序遍历、对应关系
一棵一般树
难度★★★考点树与森林、树的遍历、后根遍历、中序遍历、对应关系
一棵一般树
难度★★★★考点树与森林、树的遍历、二叉树反推、孩子兄弟法、根的孩子数
已知一棵一般树
难度★★★★★考点树与森林、森林、孩子兄弟法、二叉树性质、综合
森林
答案总览（建议完成全部题目后查看）
- 第 1 题：B
- 第 2 题：B
- 第 3 题：C
- 第 4 题：C
- 第 5 题：C
- 第 6 题：C
- 第 7 题：B
- 第 8 题：B
- 第 9 题：B
- 第 10 题：C
- 第 11 题：A
- 第 12 题：C
- 第 13 题：C
- 第 14 题：A
- 第 15 题：A
- 第 16 题：C
- 第 17 题：A
- 第 18 题：A
- 第 19 题：A
- 第 20 题：B
综合题
综合题 1｜2014 年真题第 41 题
难度：★★★★ · 分值：13 分
考点：树与森林、前序遍历、二叉树、WPL、带权路径长度、先序遍历、算法设计
二叉树的带权路径长度（WPL）是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树 T，采用二叉链表存储，结点结构为：
+--------+--------+--------+
| left | weight | right |
+--------+--------+--------+其中叶结点的 weight 域保存该结点的非负权值。设 root 为指向 T 的根结点的指针，请设计求 T 的 WPL 的算法。要求：
(1) 给出算法的基本设计思想。
(2) 使用 C 或 C++ 语言，给出二叉树结点的数据类型定义。
(3) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
参考答案与详细解析
详细解析
(1) 设计思想
答案：递归遍历二叉树，传递当前结点的深度 depth；遇到叶结点时累加 weight × depth，遇到内部结点则递归左右子树（depth+1）。
为什么这种 DFS 就能算 WPL？
WPL（Weighted Path Length）= 所有叶子的（权值 × 路径长度）之和。每个叶子的"路径长度"就是从根到该叶子的边数（也即该叶子的深度，根定为深度 0）。一次 DFS 自然地把"深度"作为递归参数向下传递：
- 进入新结点 depth+1；
- 到达叶子时（左右孩子都为 NULL）：贡献
node->weight × depth； - 内部结点不贡献——题面明确"叶结点的 weight 域保存权值"，内部结点的 weight 不计入 WPL。
实现细节：
- 主函数调用一次
wplDfs(root, 0)，根的深度从 0 开始； - 递归函数判断：
node == NULL→ return 0；- 是叶子（左右子树都空）→ return
weight × depth； - 否则 → return 左子树 WPL + 右子树 WPL。
(2) 二叉树结点的数据类型定义
c
typedef struct TreeNode {
struct TreeNode *left; // 左孩子指针
int weight; // 叶结点的权值
struct TreeNode *right; // 右孩子指针
} TreeNode;字段顺序对照题面给的结构图（left | weight | right）。
weight在内部结点不使用，但所有结点共用同一类型，便于树的统一构造与遍历。
(3) 代码实现
c
static int wplDfs(TreeNode *node, int depth) {
if (node == NULL) return 0; // 空树或空指针：贡献 0
// 判断叶结点（左右子树都为 NULL）
if (node->left == NULL && node->right == NULL) {
return node->weight * depth; // 叶子：贡献 weight × 深度
}
// 内部结点：递归累加左右子树的 WPL，深度 +1
return wplDfs(node->left, depth + 1)
+ wplDfs(node->right, depth + 1);
}
int wpl(TreeNode *root) {
return wplDfs(root, 0); // 根的深度从 0 起算
}关键点说明：
- 叶子判定 = 左右孩子都 NULL：本题二叉链表，没有"度为 1 的中间结点"作为叶子——题面默认"叶 = 左右都空"。如果是表达式树等会出现"单孩子结点"的场景，要按题意单独判。
- 根的深度从 0 起：题中"路径长度"指边数，根到自己 0 条边。如果题目改成"层数从 1 起"，把初始 depth 改 1 即可，递归形态不变。
- 递归 vs 迭代：本题用递归最自然；用迭代（BFS + 队列携带深度）也能实现，但代码繁、空间也是 O(n)，不划算。
- 复杂度：时间 O(n)，每个结点访问一次；空间 O(h)，递归栈深 = 树高。最坏（退化链状树）h = n，平均（平衡树）h = log n。
编者注（生僻术语）：WPL 是哈夫曼编码的核心评价指标。哈夫曼树就是"在所有叶子权值固定的二叉树中 WPL 最小的那棵"。本题不要求构造最优树，只要求会算 WPL——即对任意给定二叉树（可能根本不是哈夫曼树），按定义遍历求和。
综合题 2｜2016 年真题第 42 题
难度：★★★ · 分值：8 分
考点：树与森林、k叉树、正则k叉树、叶结点数、数学证明
如果一棵非空 k（k ≥ 2）叉树 T 中每个非叶结点都有 k 个孩子，则称 T 为正则 k 叉树。请回答下列问题并给出推导过程。
(1) 若 T 有 m 个非叶结点，则 T 中的叶结点有多少个？
(2) 若 T 的高度为 h（单结点的树 h = 1），则 T 的结点数最多为多少个？最少为多少个？
参考答案与详细解析
详细解析
(1) 叶结点数
答案：
推导——用「孩子总数 = 非根结点总数」这条关系：
- T 中每个非叶结点都有
- T 中除根以外的每个结点都恰好是某个非叶结点的孩子（一对一）→ 非根结点总数 =
- 设叶结点数为
因此
验证：k=2、m=3 的满二叉树，L = 3×1+1 = 4 ✓。
(2) 高度为 h 时结点数的极值
答案：最多
最多——满 k 叉树（每层都填满）：
每层结点数
最少——每层只有 1 个非叶（"瘦削"的正则 k 叉树）：
正则 k 叉树要求"每个非叶都恰好 k 个孩子"，不能少。所以从根开始一路向下：
- 第 1 层：1 个根；
- 第 2 层：根的 k 个孩子（其中 1 个是非叶，其余 k−1 个是叶）；
- 第 3 层：上一层那 1 个非叶的 k 个孩子；
- ……
- 第 h 层：上一层那 1 个非叶的 k 个孩子（全是叶）。
第 1 层 1 个，第 2..h 层各 k 个，共
验证：
- h=1：单结点，
- h=2、k=2：
- h=3、k=2：
编者注（生僻术语）：「正则 k 叉树（regular k-ary tree）」是"每个非叶都恰有 k 个孩子"的树。区分易混术语：满 k 叉树额外要求"所有叶子在同一层"——满 k 叉树一定正则，反之不然。本题叶数公式
在正则 k 叉树就够用，对满 k 叉树自然也对。
综合题 3｜2017 年真题第 41 题
难度：★★★★ · 分值：15 分
考点：树与森林、中序遍历、表达式树、中缀表达式、算法设计
请设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。例如，下列两棵表达式树作为算法输入时，输出的中缀表达式分别为 (a+b)*(c*(-d)) 和 (a*b)+(-(c-d))。
表达式树 1（中缀：(a+b)*(c*(-d))）：
text
*(+(a, b), *(c, -(_, d)))表达式树 2（中缀：(a*b)+(-(c-d))）：
text
+(*(a, b), -(_, -(c, d)))注：单目运算符
-（取负）在树里以左子树为空_、右子树为操作数表示。
二叉树结点的定义如下：
c
typedef struct node {
char data[10]; // 存储操作数或操作符
struct node *left, *right;
} BTree;要求：
(1) 给出算法的基本设计思想。
(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
参考答案与详细解析
详细解析
(1) 设计思想
答案：对表达式树做中序遍历——访问内部结点（操作符）时先输出 (、再递归左、再输出该操作符、再递归右、最后输出 )；叶结点（操作数）直接输出。但根结点外面不加括号。
为什么是"中序 + 加括号"？
中缀表达式天生就是表达式树的中序遍历。问题在于"括号"——比如 a+b*c 和 (a+b)*c 的中序遍历都是 a+b*c，但树结构不同。要无歧义还原算式，每个非叶子树都用一对括号"封装"自己就万无一失。
根不加括号的两个原因：
- 整个式子最外层无需括号（题面例子也没有）；
- 若递归时一上来就给根加括号，单目
-会产生(-d)整体在最外层，看起来变扭。
单目 -（取负）的处理：题中约定单目 - 的左子树为空、右子树为操作数。算法天然支持——递归"左子树"时若是空指针就跳过、不递归；输出顺序变成 ( - X )，正合题意（如 (-d)）。
完整流程：
- 递归参数：当前结点
node、当前递归深度depth（根 depth=0，子树 depth>0）； - 若
node为空：直接 return； - 若
node是叶子：输出node->data，return； - 否则（操作符）：
- 若
depth > 0：输出(； - 递归左子树（若不空）；
- 输出
node->data（操作符本身）； - 递归右子树；
- 若
depth > 0：输出)。
- 若
(2) 代码实现
c
typedef struct node {
char data[10];
struct node *left, *right;
} BTree;
// depth: 当前结点在树中的递归深度，根为 0
static void traverse(BTree *node, int depth, char *buf) {
if (node == NULL) return;
int isLeaf = (node->left == NULL && node->right == NULL);
if (isLeaf) {
strcat(buf, node->data); // 操作数直接输出
return;
}
if (depth > 0) strcat(buf, "("); // 非根的操作符，左侧加 (
if (node->left != NULL) traverse(node->left, depth + 1, buf);
strcat(buf, node->data); // 输出操作符
traverse(node->right, depth + 1, buf);
if (depth > 0) strcat(buf, ")"); // 非根的操作符，右侧加 )
}
void toInfix(BTree *root, char *buf) {
buf[0] = '\0';
traverse(root, 0, buf);
}用例 1 推导——*(+(a, b), *(c, -(_, d)))：
| 递归状态 | 输出累计 |
|---|---|
进根 *，depth=0，不加 ( | `` |
递归左子树 +，depth=1，加 ( | ( |
递归 a（叶）输出 a | (a |
输出 + | (a+ |
递归 b（叶）输出 b | (a+b |
+ 子树结束，加 ) | (a+b) |
输出根 * | (a+b)* |
递归右子树 *，depth=1，加 ( | (a+b)*( |
递归 c（叶） | (a+b)*(c |
输出 * | (a+b)*(c* |
递归右孙 -（单目），depth=2，加 ( | (a+b)*(c*( |
| 左子空，跳过 | (a+b)*(c*( |
输出 - | (a+b)*(c*(- |
递归 d（叶） | (a+b)*(c*(-d |
- 子树结束，加 ) | (a+b)*(c*(-d) |
* 子树结束，加 ) | (a+b)*(c*(-d)) |
✓ 与题面一致。
关键点说明：
- 括号成对出现的位置：进入非叶非根时加
(，离开非叶非根时加)，绝对配对，不会少一只多一只。 - 单目
-不需特殊代码：题中规定单目-的左子树为空，递归 left 时直接node == NULLreturn；接着输出-再递归右就得到(-X)，与"先 ( 再 op 再右子树 再 )"流水线一致。 - 复杂度：时间 O(n)（n 个结点各访问一次，
strcat单次累加是常数次字符）；空间 O(h)（递归栈深 = 树高）。
综合题 4｜2020 年真题第 42 题
难度：★★★ · 分值：10 分
考点：哈夫曼树与编码、树与森林、前缀编码、二叉树、译码、数据结构设计
任一个字符的编码都不是其它字符编码的前缀，则称这种编码具有前缀特性。现有某字符集（字符个数 ≥ 2）的不等长编码，每个字符的编码均为二进制的 0、1 序列，最长为 L 位，且具有前缀特性。请回答下列问题：
(1) 哪种数据结构适宜保存上述具有前缀特性的不等长编码？
(2) 基于你所设计的数据结构，简述从 0/1 串到字符串的译码过程。
(3) 简述判定某字符集的不等长编码是否具有前缀特性的过程。
参考答案与详细解析
详细解析
(1) 适合存放前缀编码的数据结构
答案：二叉树（编码树 / 前缀码 trie）。
构造规则：
- 每个字符存放在一个叶子结点——保证从根到该叶子的 0/1 路径就是该字符的编码；
- 内部结点不存字符——只起"路径分叉"作用；
- 左分支记 0，右分支记 1（约定即可，反过来也行）；
- 树最多有
为什么这种结构天然就是"前缀码"：因为字符只在叶子。叶子的祖先全是内部结点，任何字符的编码（根→叶子路径）都不可能是另一字符编码（也是根→另一叶子路径）的前缀——否则前者那个叶子会出现在后者的路径中间，与"叶子"地位矛盾。
编者注（生僻术语）：哈夫曼树（Huffman tree）就是这种"编码树"的一种特殊构造（按字符频率构造使加权路径长度最短）。本题不要求最优编码，任何"字符全在叶子"的二叉树都满足前缀特性。
(2) 译码过程
答案：从根开始，按位读 0/1 串，0 走左、1 走右；遇到叶子就输出该叶子上的字符并回到根；继续读下一位。直到 0/1 串读完。
伪代码：
text
cur ← 根
result ← 空字符串
对 0/1 串中每一位 b：
若 b = 0：cur ← cur.left
否则： cur ← cur.right
若 cur 是叶子：
result ← result + cur.char
cur ← 根 // 回到根，准备下一个字符
返回 result关键点：
- 由于编码具备前缀特性，每次到达叶子的时刻是唯一确定的——没有"提前停下"或"该停而没停"的歧义；
- 若读完 0/1 串时
cur不在根（说明最后一段路径走了一半还没到叶子），则 0/1 串本身有问题（不是合法编码）； - 时间复杂度
(3) 判定一组不等长编码是否具备前缀特性
答案：把每个编码作为一条 0/1 路径插入空二叉树，过程中违反以下两条之一即不具备前缀特性，全部插完未违反则具备：
- "穿越"已有叶子：插入新编码时，途中走到了一个已经被标记为叶子的结点（说明已有某字符的编码是新编码的前缀）；
- 新叶子位置已是分叉：把新编码的最后一位走到的结点要标为新叶子，但这个结点已经有左/右孩子（说明新编码是某已有编码的前缀）。
伪代码：
text
建一棵只有根的空树
对每个字符的编码 code：
cur ← 根
对 code 中每一位 b：
若 cur 已被标记为叶子：返回 "不具备前缀特性" // 情况 1
若 cur 沿 b 方向无孩子：建该孩子
cur ← cur 沿 b 方向的孩子
若 cur 已有孩子：返回 "不具备前缀特性" // 情况 2
把 cur 标记为叶子（绑定到当前字符）
返回 "具备前缀特性"关键点说明：
- 两种违反情况对称：情况 1 是"老编码是新编码前缀"；情况 2 是"新编码是老编码前缀"；
- 复杂度
- 替代方法——也可以两两比较所有编码对，看一个是否是另一个的前缀串。但这要
综合题 5｜巩固题
难度：★★★ · 分值：12 分
考点：树与森林、树、孩子兄弟链表、树高、递归、算法设计
设树 T 采用孩子兄弟链表存储，结点结构如下：
c
typedef struct CSNode {
int data;
struct CSNode *firstChild;
struct CSNode *nextSibling;
} CSNode;root 指向 T 的根，约定 root->nextSibling == NULL（根没有兄弟），空树以 root == NULL 表示。请设计一个时间复杂度
(1) 给出算法的基本设计思想；
(2) 采用 C 语言描述算法，关键之处给出注释；
(3) 说明算法的时间复杂度与空间复杂度。
函数签名（与 OJ wrapper 一致）：
c
int treeHeight(CSNode *root);约束：
测试覆盖维度：测试用例除常规情况外，还包含以下边界，WA 时建议逐个排查：
- 链状树：每个非叶节点恰有 1 个孩子，高度 =
- 扁平树：根有
- 多分叉非平衡树：某分支深而另一分支浅，验证
max(子高, 兄弟高)取得正确； - 较大规模：
参考答案与详细解析
详细解析
思路分析
解法 1（朴素思路）：先把孩子兄弟链表"还原"为通用树再求高度
考生看到陌生的存储结构会本能地想"先转回熟悉的形式"——把每个结点的 firstChild → nextSibling → nextSibling → ... 这条兄弟链显式收集为孩子数组，建立一棵每个结点持有"孩子列表"的通用树，再做 DFS 求高度。
- 时间：扫一遍兄弟链
- 空间：需要
问题：完全多余的中转层。孩子兄弟链表的 firstChild + nextSibling 已经能在不重构数据结构的前提下被原地递归处理——只要正确区分两种边的语义。
解法 2（最优）：原地双向递归——firstChild 加 1，nextSibling 不加
核心洞察 ——「firstChild 走深，nextSibling 走宽」：
孩子兄弟链表里只有两种指针，但它们在原树里的语义截然不同：
firstChild走一步 = 在原树中下移一层——递归得到的子树高度需要nextSibling走一步 = 在原树中保持在同一层（横向遍历兄弟）——递归得到的"以兄弟为根的子结构高度"已经包含了与当前节点同层的那一层，直接拿来比较，绝不- 当前节点子树的最终高度 =
为什么递归到 nextSibling 不加 1（命题人复盘）：
在原树语义里，兄弟节点和当前节点处于同一层；递归函数 treeHeight(sibling) 是"以兄弟节点作为虚拟根、把它自己的孩子兄弟子结构当作一棵新的树"算出的高度。这棵新树的"第 1 层"是兄弟自己——而兄弟本来与当前节点同层，于是 treeHeight(sibling) 的返回值已经表达了"从这一层往下的最大层数"，当前节点不再贡献新的一层。
举例：原树 = 根 R 有三个孩子 A、B、C（全是叶子）。孩子兄弟链表表示：
R.firstChild → A.nextSibling → B.nextSibling → C
A.firstChild = B.firstChild = C.firstChild = NULL逐步递归：
若错写成 nextSibling 也
两解法对比
| 维度 | 解法 1 重建通用树 | 解法 2 原地双向递归 |
|---|---|---|
| 时间复杂度 | ||
| 空间复杂度 | ||
| 思维难度 | 低（绕回熟悉形式） | 中（必须想清两种边的语义差异） |
| 实现风险 | 中（动态数组 / 链表收集易写错） | 低（两行递归 + 一次取 max） |
| 适配考研答题 | 啰嗦（多写 20 行） | 紧凑（5 行核心逻辑） |
考研推荐解法 2。下方参考实现给出解法 2。
参考实现（C）
c
int treeHeight(CSNode *root) {
if (root == NULL) return 0; /* 空（子）树：高度 0 */
int childH = treeHeight(root->firstChild); /* ① firstChild 走一步 = 下一层 */
int siblingH = treeHeight(root->nextSibling); /* ② nextSibling 走一步 = 同一层 */
int hThis = 1 + childH; /* ③ 当前节点这一支的高度，需 +1 */
return hThis > siblingH ? hThis : siblingH; /* ④ 与兄弟分支取大 */
}关键点说明：
- 不需要"叶子判断"：经典二叉树递归往往在叶子（左右孩子都 NULL）处显式处理，本题不必——
treeHeight(NULL) = 0已经吞掉了所有空指针，叶子结点的firstChild为 NULL 时自然得到childH = 0，最终1 + 0 = 1，正是叶子那一层的贡献。 +1只出现一次且只对childH：这是本题的单点真理。任何形式的"也给 siblingH 加 1"或"对结果再 +1"都会破坏层数语义。- 顺序无关：①②可以交换，最终都靠 ④ 取 max 收敛，但易读性上"先深后宽"更自然。
- 不需手动维护层数参数：与 ds-2014-41（WPL）必须传
depth不同——求高度只关心"最深距离"，可以从叶子向上累加；传递深度反而冗余。这是同套递归框架在"求最深处的值（高度）"和"求路径上的累加（WPL）"两种任务下的对称差异。
复杂度证明
时间复杂度
孩子兄弟链表中，每个结点的 firstChild 边恰好被 treeHeight 递归调用一次（作为某个父结点的 ①），每个结点的 nextSibling 边也恰好被递归调用一次（作为某个左侧兄弟的 ②）。一棵
每一帧函数体内是常数次比较与赋值。
空间复杂度
仅递归栈占用。设原树高度为 treeHeight(root->nextSibling) 会沿着 nextSibling 链不断展开，扁平树（根有
其中
易错点
本题不在"想不到递归"——而在于**「兄弟当孩子」**这条经典认知陷阱：很多考生看到 nextSibling 也是指针就把它和 firstChild 同等对待，一律 1 + 递归值 —— 这等价于把同层兄弟当成了下一层节点，会把扁平树（高度应为 2）算成
盲区 A：「兄弟当孩子」（最高频，写一行错满分）
一战考生看到
nextSibling也是指针，会很本能地写成对称的两次int childH = treeHeight(root->firstChild); int siblingH = treeHeight(root->nextSibling); return 1 + (childH > siblingH ? childH : siblingH); /* 错！对 siblingH 也加了 1 */错误推演：再看上文"根 R 有三个孩子 A、B、C"的扁平树。按错解推：
正解：
firstChild才是层数变化的方向——只有它的递归值要nextSibling是同层游走，递归值直接进入max比较。这条规则与本套约定中"原树语义优先于孩子兄弟链表表面形态"是同一件事。本盲区命名为「兄弟当孩子」，与 [[forest-tree-conversion]] / [[tree-traversal]] 等 KP 出现"森林 / 树 / 二叉树等价转换"题时同源回扣。盲区 B：「+1 给错位置」
考生意识到了"只给 childH 加 1"，但具体写成：
creturn (1 + childH) > (1 + siblingH) ? (1 + childH) : (1 + siblingH);或
cint h = childH > siblingH ? childH : siblingH; return 1 + h;错误推演：第一种写法等价于盲区 A；第二种写法（先 max 后 +1）则会把"兄弟链高度"也整体上抬一层。仍以扁平树为例：
正解：唯一正确的位置是"
childH + 1再与siblingH比"——+1只能作用于子分支这一支，绝不能下放到 max 之外。盲区 C：「单节点高度算成 0」
考生写：
cif (root == NULL || (root->firstChild == NULL && root->nextSibling == NULL)) return 0;把"叶子节点"也当成空树早返回。
错误推演：
正解：只有
root == NULL才返回 0；叶子节点的firstChild为 NULL 这件事会通过treeHeight(NULL) = 0自动处理，主体函数不要在外面提前 return。这条约定与 ds-2014-41 WPL 题"node == NULL才 return 0、叶子节点要正常贡献"完全同源——空指针 ≠ 叶子。盲区 D：「递归参数化深度，混入 2014-41 的 WPL 风格」
考生看过 2014-41 WPL 那种
void wplDfs(TreeNode *node, int depth)的写法，搬过来写：cint treeHeight(CSNode *root, int depth) { if (root == NULL) return depth; ... }错误推演：用
depth参数追踪当前节点的层数没错，但本题求的是"最大层数"——必须在递归过程中全局取 max 或返回一个值参与父层比较。若仅按 2014-41 的写法返回depth，叶子节点返回的是自己那一层的depth，但上层递归调用treeHeight(child, depth + 1)拿到这个值后还要决定怎么和兄弟分支比较——很容易写成"取最后一次访问的叶子层数"而非"所有叶子层数的最大值"，从而漏掉非最深叶子之外其他分支的贡献。正解：求高度只需要"自底向上返回子树高度"这一招，不需要往下传递 depth——叶子返回 1（即
1 + 0），其上每层叠加比较即可。这是同套递归框架在"路径累加（WPL，自顶向下传 depth）"与"取最深（高度，自底向上返回 h）"两种任务下的范式差异。把两种范式混用是本盲区的根源。盲区 E：「兄弟链递归栈深没意识」（思维层，写得出但跑大 case 才暴露）
考生写完递归觉得"反正树高
错误推演：扁平树（
treeHeight(root->nextSibling)把nextSibling链顺着递归展开，本质上和处理一条 999 长的链状结构同等开销。在默认 1 MB 栈（每帧约 32–64 字节）下，正解：明确孩子兄弟链表的递归栈深 =
nextSibling的递归改写为while迭代以省栈，仅保留firstChild的递归。这条认知与 [[singly-linked-list]] 题"链表遍历用迭代不用递归免爆栈"是同一道理——所有"链表形态"的递归都隐含线性栈深风险。本盲区命名为「链式递归吞栈」，在 KMP / 单调栈 / 二叉树迭代写法等场景下也有回扣。
完成清单
复盘
- 哪道题最容易因遍历顺序、层次口径或结构关系判断失误？
- 我能否不用背答案，重新画树或写出访问过程？
- 如果题目改变一个条件，原结论是否仍成立？