目标

• 独立辨析二叉树基础（性质与存储）中的核心概念、结构性质与遍历关系；
• 对选择题写出排除干扰项的依据，而不只记忆答案字母；
• 对源文档提供的综合题完成推导、算法设计或复杂度分析。

前置知识

建议先阅读第 4 章对应教材，再开始本组练习。

环境、输入与预期输出

• 环境：任意现代浏览器；综合题建议准备纸笔或本地编辑器。
• 输入：20 道四选一选择题，5 道综合题。
• 预期输出：一份独立作答记录，以及每道错题或综合题的完整推理过程。

作答方法

1. 选择题先独立判断并记录依据，再点击“提交答案”；
2. 提交后核对正确答案和解析，做错的题使用“重新作答”；
3. 综合题先完成推导、伪代码或代码，再展开参考答案逐项核对；
4. 对重复出现的真题，说明它在不同知识主题下分别考查了什么。

选择题

答题进度已答 0/20正确 0

第 1 题

难度★★★考点二叉树基础（性质+存储）、树和森林的遍历、二叉树遍历、RNL、遍历方式辨析

给定二叉树如下图所示。设 N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树。若遍历后的结点序列是 3，1，7，5，6，2，4，则其遍历方式是( )。

1(2(4, 5(6, 7)), 3)

请选择一个答案

ALRN

BNRL

CRLN

DRNL

第 2 题

难度★★★考点二叉树基础（性质+存储）、完全二叉树、节点计数、第N层叶子

已知一棵完全二叉树的第 6 层(设根为第 1 层)有 8 个叶结点，则该完全二叉树的结点个数最多是()。

请选择一个答案

A39

B52

C111

D119

第 3 题

难度★★★★考点二叉树基础（性质+存储）、树与森林、森林转二叉树、左孩子右兄弟、关系判断

将森林转换为对应的二叉树，若在二叉树中，结点 u 是结点 v 的父结点的父结点，则在原来的森林中，u 和 v 可能具有的关系是( )。

I. 父子关系

II. 兄弟关系

III. u 的父结点与 v 的父结点是兄弟关系

请选择一个答案

A只有 II

BI 和 II

CI 和 III

DI、II 和 III

第 4 题

难度★★★★考点二叉树基础（性质+存储）、后序遍历、线索二叉树、线索化

下列线索二叉树的线索描述中（箭头 x→y 表示从 x 的空指针域引出线索），符合后序线索树定义的是( )。

结构（文字版）：四个选项使用同一棵二叉树（节点皆为空圆，题面仅用字母标记 a/b/c/d 用于区分）。

• 树形：a 为根，b 是 a 的左孩子，c 是 a 的右孩子，d 是 b 的右孩子（叶节点）
• 后序遍历序列：d → b → c → a
• 共有 5 个线索位——b 的左指针、c 的左/右指针、d 的左/右指针；四个选项的差异就在这 5 个线索的指向是否符合后序线索树定义，请根据各选项列出的 5 条虚线线索判断

请选择一个答案

Ab→a；c→b、d；d→Null、c

Bb→Null；c→a、Null；d→b、a

Cb→a；c→d、Null；d→a、c

Db→d；c→b、a；d→Null、b

第 5 题

难度★★★考点二叉树基础（性质+存储）、哈夫曼树与编码、哈夫曼树、完全二叉树、树的性质

对 n (n≥ 2) 个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是( )。

请选择一个答案

A该树一定是一棵完全二叉树

B树中一定没有度为 1 的结点

C树中两个权值最小的结点一定是兄弟结点

D树中任一非叶结点的权值一定不小于下一层任一结点的权值

第 6 题

难度★★考点二叉树基础（性质+存储）、完全二叉树、叶子数计算、度数关系

若一棵完全二叉树有 768 个结点，则该二叉树中叶结点的个数是()

请选择一个答案

A257

B258

C384

D385

第 7 题

难度★★★考点二叉树基础（性质+存储）、树转二叉树、左孩子右兄弟、无右孩子节点

已知一棵有 2011 个结点的树，其叶结点个数为 116，该树对应的二叉树中无右孩子的结点个数是( )。

请选择一个答案

A115

B116

C1895

D1896

第 8 题

难度★★★考点二叉树基础（性质+存储）、二叉树、卡特兰数、计数

先序序列为 a,b,c,d 的不同二叉树的个数是()。

请选择一个答案

A13

B14

C15

D16

第 9 题

难度★★考点前序遍历、中序遍历、二叉树基础（性质+存储）、二叉树遍历、先序遍历

要使一棵非空二叉树的先序序列与中序序列相同，其所有非叶节点须满足的条件是( )。

请选择一个答案

A只有左子树

B只有右子树

C结点的度均为 1

D结点的度均为 2

第 10 题

难度★★★考点二叉树基础（性质+存储）、后序遍历、二叉树重构、层次

已知一棵二叉树的树形如下图所示，其后序序列为 e, a, c, b, d, g, f，树中与结点 a 同层的结点是( )。

1(2(_, 4(6, _)), 3(5(_, 7), _))

编号仅为表述方便（按层序遍历自顶向下、自左向右标注），原题节点皆为空圆。结构特征：根有左右两个孩子；左孩子只有右子，且其右子只有左子；右孩子只有左子，且其左子只有右子。共 7 个节点，分布在 4 层（1 / 2 / 2 / 2）。

请选择一个答案

Ac

Bd

Cf

Dg

第 11 题

难度★★考点二叉树基础（性质+存储）、满二叉树、叶结点、结点总数

设一棵非空完全二叉树 T 的所有叶结点均位于同一层，且每个非叶结点都有 2 个子结点。若 T 有 k 个叶结点，则 T 的结点总数是( )。

请选择一个答案

A$2k-1$

B$2k$

C$k^2$

D$2^{k-1}$

第 12 题

难度★★★考点二叉树基础（性质+存储）、树、二叉树转换、后根遍历

若将一棵树 T 转化为对应的二叉树 BT，则下列对 BT 的遍历中，其遍历序列与 T 的后根遍历序列相同的是( )。

请选择一个答案

A先序遍历

B中序遍历

C后序遍历

D按层遍历

第 13 题

难度★★★考点二叉树基础（性质+存储）、二叉树、顺序存储、完全二叉树编号

对于任意一棵高度为 $5$ 且有 $10$ 个结点的二叉树，若采用顺序存储结构保存，每个结点占 $1$ 个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元数量至少是( )。

请选择一个答案

A31

B16

C15

D10

第 14 题

难度★★★★考点二叉树基础（性质+存储）、中序遍历、二叉树、相邻结点关系

若结点 p 与 q 在二叉树 T 的中序遍历序列中相邻，且 p 在 q 之前，则下列 p 与 q 的关系中，不可能的是( )。

I. q 是 p 的双亲

II. q 是 p 的右孩子

III. q 是 p 的右兄弟

IV. q 是 p 的双亲的双亲

请选择一个答案

A仅 I

B仅 III

C仅 II、III

D仅 II、IV

第 15 题

难度★★★考点二叉树基础（性质+存储）、哈夫曼树与编码、哈夫曼树、定长编码、二叉树性质

对任意给定的含 n (n > 2) 个字符的有限集 S, 用二叉树表示 S 的哈夫曼编码集和定长编码集，分别得到二叉树 T1 和 T2。下列叙述中，正确的是 ( )。

请选择一个答案

AT1 与 T2 的结点数相同

BT1 的高度大于 T2 的高度

C出现频次不同的字符在 T1 中处于不同的层

D出现频次不同的字符在 T2 中处于相同的层

第 16 题

难度★★★考点二叉树基础（性质+存储）、前序遍历、后序遍历、二叉树、先序遍历、遍历序列重建

已知一棵二叉树的树形如下图所示，若其后序遍历为 f, d, b, e, c, a，则其先序序列为( )。

1(2(4(_, 6), 5), 3)

结构（文字版）（节点按层序由 1 到 6 编号；编号仅为表述方便，原题节点皆为空圆）：根 1 的左孩子是 2、右孩子是 3（叶子）；2 的左孩子是 4、右孩子是 5（叶子）；4 没有左孩子，右孩子是 6（叶子）。

请选择一个答案

Aa, e, d, f, b, c

Ba, c, e, b, d, f

Cc, a, b, e, f, d

Dd, f, e, b, a, c

第 17 题

难度★★★★考点二叉树基础（性质+存储）、中序遍历、线索二叉树、二叉树、前驱后继

p、q、v 都是二叉树 T 中的结点，二叉树 T 的中序遍历为 ···, p，v，q，··· ，其中 v 有两个孩子结点，则下列说法正确的是( )。

请选择一个答案

Ap 没右孩子，q 没左孩子

Bp 没右孩子，q 有左孩子

Cp 有右孩子，q 没左孩子

Dp 有右孩子，q 有左孩子

第 18 题

难度★★★★考点二叉树基础（性质+存储）、二叉树、顺序存储、父子下标关系

若二叉树的节点值均为正整数，采用顺序存储方式保存在数组 R 中，用 -1 表示节点不存在，则下列数组中，不能表示一棵二叉树的是()。

请选择一个答案

AR[] = {20, 15, 40, -1, -1, 35}

BR[] = {15, 40, 10, 18, 35, -1, -1}

CR[] = {15, 40, 10, -1, -1, -1, 12}

DR[] = {17, 20, 35, -1, 18, 45, -1, -1, 19, 27}

第 19 题

难度★★★考点二叉树基础（性质+存储）、完全二叉树、森林转二叉树、表达式树

下列关于二叉树及森林的叙述中，正确的是？( )。

请选择一个答案

A完全二叉树不存在度为 1 的结点

B任意一个森林可以转换为一棵二叉树。

C二叉树的分支结点个数比叶结点个数少

D链式树的根中保存的是最先计算的运算符

第 20 题

难度★★★★考点二叉树基础（性质+存储）、树与森林、森林转二叉树、孩子兄弟法、二叉树高度

森林 F 中有 5 颗树，其节点个数分别为 2、3、4、5、7，森林中树的次序可以任意，问 F 对应的二叉树最小高度为多少？

请选择一个答案

A5

B6

C8

D10

答案总览（建议完成全部题目后查看）

1. 第 1 题：D
2. 第 2 题：C
3. 第 3 题：B
4. 第 4 题：D
5. 第 5 题：A
6. 第 6 题：C
7. 第 7 题：D
8. 第 8 题：B
9. 第 9 题：B
10. 第 10 题：B
11. 第 11 题：A
12. 第 12 题：B
13. 第 13 题：A
14. 第 14 题：B
15. 第 15 题：D
16. 第 16 题：A
17. 第 17 题：A
18. 第 18 题：D
19. 第 19 题：B
20. 第 20 题：B

综合题

综合题 1｜巩固题

难度：★★★ · 分值：12 分

考点：二叉树基础（性质+存储）、二叉树性质、n0=n2+1、完全二叉树、满二叉树、度数和

本套统一约定（与 kp-binary-tree-basics-001 ~ 017 一致）：

• 高度定义：空树高 0；单结点高 1；结点自身高 = $max$(左子树高, 右子树高) + 1
• 节点的度 = 该节点的孩子数（0/1/2 三种）；二叉树中 $n_d$ 表示度为 $d$ 的节点数
• 二叉树用通行约定：每个节点有"左孩子指针"与"右孩子指针"两个独立位置，左右孩子位置可区分

(1) 设二叉树 $T$ 共有 $n=199$ 个节点，其中度为 1 的节点数 $n_1=60$。

a. 用"各结点的度之和 = 边数 = $n-1$"（本题约定：结点的度 = 孩子数）这一恒等式，推出 $n_0$、$n_1$、$n_2$ 三者之间的关系式 $n_0=n_2+1$。

b. 在 $n=199$、$n_1=60$ 给定下，求 $T$ 的叶节点数 $n_0$ 与度为 2 的节点数 $n_2$。

(2) 设另有一棵高度为 $h$ 的完全二叉树 $T^{\prime }$。

a. 写出 $T^{\prime }$ 的节点数 $n$ 与高度 $h$ 之间的不等式关系（含上下界）。

b. 当 $n=200$ 时求 $T^{\prime }$ 的高度 $h$。

c. 当 $n=200$ 时分别求 $T^{\prime }$ 的 $n_0$、$n_1$、$n_2$。

(3) 设有一棵高度为 $h$ 的满二叉树 $T^{″}$，写出 $T^{″}$ 的节点数 $n$ 与高度 $h$ 的精确等式，并据此说明 $T^{″}$ 中是否可能出现度为 1 的节点。

参考答案与详细解析

详细解析

(1) n0 = n2 + 1 推导与本题应用

(1a) 公式推导

思路双线齐发：

• 节点视角：所有节点要么是叶子（度 0）、要么有一个孩子（度 1）、要么有两个孩子（度 2）。三类不重不漏：

  $$\begin{array}{}\text{(I)}& n_0+n_1+n_2=n\end{array}$$

• 边视角：二叉树有 $n$ 个节点、$n-1$ 条边（一棵树的标志性性质：$|E|=|V|-1$）。从父向子数边：每个度为 1 的节点贡献 1 条边、度为 2 的节点贡献 2 条边、叶节点贡献 0 条边。故：

  $$\begin{array}{}\text{(II)}& n_1+2n_2=n-1\end{array}$$

  编者注（易混）：数据结构里"结点的度"= 孩子数（只数向下的边），所以各结点的度之和 = 边数 = $n-1$。图论里"顶点的度"= 关联边数（连父亲的那条也算），那套口径下才有"度数和 = 边数 × 2 = $2(n-1)$"。两者差的这个 2 倍不是谁算错了，而是数的东西不同——本题及 408 的二叉树性质题一律用前者。

把式 (I) 中的 $n$ 代入式 (II)：

$$n_1+2n_2=(n_0+n_1+n_2)-1$$

两边消去 $n_1$、$n_2$：

$$\begin{array}{}\text{(III)}& n_2=n_0-1⟺\boxed{{\displaystyle n_0=n_2+1}}\end{array}$$

这个关系式对任何非空二叉树都成立（与是否完全 / 是否平衡 / 是否带头无关），是后续 (1b) (2c) 的解题根基。

(1b) 求 $n_0$ 与 $n_2$

把 $n_1=60$ 代入式 (I)：

$$n_0+n_2=n-n_1=199-60=139$$

联立式 (III) $n_0=n_2+1$：

$$\{\begin{array}{l}{n}_0+n_2=139\\ n_0-n_2=1\end{array}⟹\{\begin{array}{l}{n}_0=70\\ n_2=69\end{array}$$

验算：$70+60+69=199✓$；$60+2\cdot 69=60+138=198=n-1✓$。

(2) 完全二叉树 $T^{\prime }$

(2a) 节点数 $n$ 与高度 $h$ 的不等式

完全二叉树定义：除最后一层外每层节点数都满（即第 $k$ 层有 $2^{k-1}$ 个节点），且最后一层的节点从左侧连续排列。

记 $T^{\prime }$ 的高度为 $h$，则：

• 下界：第 1..$h-1$ 层都满 → 至少 $1+2+4+\cdots +2^{h-2}=2^{h-1}-1$ 个节点；再加上最后一层至少 1 个（否则 $T^{\prime }$ 高度不到 $h$）→ $n\ge 2^{h-1}$
• 上界：第 1..$h$ 层全满 → 至多 $2^h-1$ 个节点

$$\boxed{{\displaystyle 2^{h-1}\le n\le 2^h-1}}$$

等价改写（对求 $h$ 更直接）：

$$h=\lfloor {\log }_{2}n\rfloor +1$$

(2b) 当 $n=200$ 时求 $h$

${\log }_{2}200\approx 7.64$，$\lfloor 7.64\rfloor +1=8$。验证：$2^{8-1}=128\le 200\le 2^8-1=255✓$。

$$h=8$$

(2c) 当 $n=200$ 时求 $n_0$、$n_1$、$n_2$

Step 1: 分层节点数

层级	1	2	3	4	5	6	7	8
满层节点数	1	2	4	8	16	32	64	—

前 7 层全满 = $2^7-1=127$ 个节点；第 8 层（最后一层）= $200-127=73$ 个节点。

Step 2: 第 8 层 73 个叶子的分布

完全二叉树最后一层从左排列。第 8 层共 73 个叶节点，全是叶子；它们挂在第 7 层的前若干个节点下：

• 前 36 个第 7 层节点各挂 2 个孩子：贡献 $36\times 2=72$ 个第 8 层节点；
• 第 37 个第 7 层节点挂第 73 个第 8 层节点（只有左孩子）：贡献 1 个；
• 剩下 $64-37=27$ 个第 7 层节点无孩子，自身就是叶子。

第 7 层节点角色	数量	度
都有左右孩子（左 + 右）	36	2
只有左孩子	1	1
无孩子	27	0

Step 3: 汇总三类节点数

度	来源	数量
0（叶子）	第 8 层全部 73 + 第 7 层无孩子的 27	$73+27=\mathbf{100}$
1（一个孩子）	第 7 层只有左孩子的 1 个	$\mathbf{1}$
2（两个孩子）	第 1..6 层全部 $1+2+4+8+16+32=63$ + 第 7 层有 2 孩子的 36	$63+36=\mathbf{99}$

验算：$100+1+99=200✓$；$n_0=n_2+1$ ⇒ $100=99+1✓$。

重要观察：完全二叉树中 $n_1$ 至多为 1——只有"最后一层节点数为奇数"时存在 1 个度为 1 的节点；若最后一层节点数为偶数，则 $n_1=0$。这是完全二叉树相对一般二叉树的特殊结构性质。

(3) 满二叉树 $T^{″}$

满二叉树定义：高度为 $h$ 的所有层都填满，即每层 $k$ 都恰好有 $2^{k-1}$ 个节点。

节点总数：

$$n=1+2+4+\cdots +2^{h-1}=\boxed{{\displaystyle 2^h-1}}$$

满二叉树中是否存在度为 1 的节点：

• 第 $h$ 层（最后一层）的所有节点都是叶子（度 0），共 $2^{h-1}$ 个
• 第 1..$h-1$ 层的每个节点都恰好有 2 个孩子（因为下一层是满的），度都是 2
• 故 $n_1=0$（满二叉树不存在度为 1 的节点）

验算：$n_0=2^{h-1}$，$n_2=2^{h-1}-1$（前 $h-1$ 层节点总数 $2^{h-1}-1$），$n_0=n_2+1✓$。

易错点

1. 盲区 A：「$n_0=n_2+1$ 公式记反」

   一战考生考场紧张容易记成 $n_2=n_0+1$ 或 $n_0=n_1+1$。前者会让 (1b) 算出 $n_0=69$、$n_2=70$（位置互换、答案错位 1）；后者用 $n_0-n_1=1$ 推 $n_0=61$，整张表崩溃。

   错误推演：把 $n_2=n_0+1$ 代入 (1b)，$n_0+(n_0+1)=139\Rightarrow n_0=69$。结果看似合理但与"叶节点最少"的直觉相悖：度为 2 的内部节点不会比叶子还多（除非是退化二叉树）。

   正解共识：记忆锚点是"二叉树有 $n-1$ 条边"——叶子是"被指向但不指向他人"的，度 2 节点是"指向两人"。每条边至少有一个叶子端"输入"，每个度 2 节点"输出"两条边——必然叶子比度 2 多 1 个（多出来的那个是根节点链外那条不存在的边的"虚位"）。这条直觉锚点几乎不会记反方向。

   元层共识：建立「度数和恒等式」与 [[critical-path「ve/vl 方向取反」]] 的同源对偶——都是公式方向性盲区，根本破法都是"绑物理意义"而非"死记顺序"。

2. 盲区 B：「完全二叉树与满二叉树性质混用」

   一战考生看到题目说"完全二叉树"，下意识套"$n=2^h-1$"（其实那是满二叉树）；或看到"满二叉树"用"$2^{h-1}\le n\le 2^h-1$"（那是完全二叉树）。两者结论差别极大——本题 $n=200$ 若被错用满二叉树公式 $200=2^h-1$，$h={\log }_{2}201$ 不是整数，立刻看出矛盾，但考生常常将就着写"$h$ 约为 7.65 取 8"，跟正解碰巧一致但思路完全错。

   错误推演：若 $n=255$（恰好满二叉树），用完全二叉树公式仍能算对 $h=8$；用满二叉树公式 $255=2^8-1$ 也对。但 $n=200$ 时只有完全二叉树存在，满二叉树不存在 $n=200$ 的实例——考生若硬套满二叉树公式会得出"不存在这种树"的反例感。

   正解共识：两类树的边界条件——

   • 满二叉树：每层都满 → $n=2^h-1$（精确）
   • 完全二叉树：除最后一层外全满，最后一层左对齐 → $2^{h-1}\le n\le 2^h-1$（区间）
   • 满二叉树 ⊆ 完全二叉树（每棵满二叉树都是完全二叉树，反之不一定）

3. 盲区 C：「完全二叉树 $n_1$ 一定是 0 或 1，但分不清何时是 0、何时是 1」

   有同学知道"完全二叉树 $n_1\in \{0,1\}$"，但记不住"何时为 1"。

   错误推演：本题 $n=200$，若以为 $n_1=0$，那 $n_0+n_2=200$、$n_0=n_2+1\Rightarrow n_0=100.5$ 不是整数——立刻看出矛盾，但答题已偏。

   正解共识：判定法——

   • 最后一层节点数 = $n-(2^{h-1}-1)$
   • 若该值为偶数 → 最后一层挂 "成对" 在第 $h-1$ 层，$n_1=0$
   • 若该值为奇数 → 最后一层最后一个节点是孤立的左孩子，挂它的第 $h-1$ 层那个节点是度为 1，$n_1=1$
   • 本题最后一层 73 个（奇数）→ $n_1=1$
   • 更快的判定法：用 $n_0=n_2+1$ 反推——若 $n-1$ 是偶数（$n$ 是奇数），可凑出 $n_0$、$n_2$ 都是整数让 $n_1=0$；若 $n-1$ 是奇数（$n$ 是偶数），必须 $n_1\ge 1$（且完全二叉树性质强制 $n_1=1$）。简口诀：$n$ 偶 → $n_1=1$，$n$ 奇 → $n_1=0$（仅适用于完全二叉树）。

4. 盲区 D：「度数和算成节点和」

   一战考生在推导 (1a) 时常常错把 "$n_1+2n_2$" 写成 "$n_0+n_1+n_2$"（即把"度数和"与"节点和"混为一谈）。两者都是"对节点求和"，但前者按"度"加权，后者按"个数"。

   错误推演：若 $n_1+2n_2$ 错写成 $n_0+n_1+n_2$，那 (II) 式就变成 $n=n-1$，立刻发现是恒等于假的等式——但考生常常忽视这个"恒不成立"的信号，继续往下推得出错误的 $n_0=n_2$ 或别的关系。

   正解共识：度数和就是"每个节点贡献多少条出边"——加权而非计数。节点和才是"每个节点算 1 次"。两者出发点不同，混用会让公式坍塌。

   元层共识：建立「计数 vs 加权和」家族——与 hash-open-addressing「ASL 分母用关键字数还是 H 输出范围」、critical-path「事件级 vs 活动级余量」同属"统计口径错位"红线。

最终答案

• (1a) $n_0=n_2+1$（推导见上）
• (1b) $n_0=70$，$n_2=69$
• (2a) $2^{h-1}\le n\le 2^h-1$
• (2b) $h=8$
• (2c) $n_0=100$，$n_1=1$，$n_2=99$
• (3) $n=2^h-1$；满二叉树中不存在度为 1 的节点（$n_1=0$）

综合题 2｜巩固题

难度：★★★ · 分值：12 分

考点：二叉树基础（性质+存储）、二叉树、叶节点、递归、二叉链表、算法设计

设二叉树以二叉链表方式存储，节点定义如下（C 语言）：

typedef struct BiTNode {
    int                data;
    struct BiTNode    *lchild;
    struct BiTNode    *rchild;
} BiTNode, *BiTree;

请你设计一个算法，给定二叉树根指针 T，返回该二叉树中叶节点的个数（左孩子指针与右孩子指针都为空的节点）。空树的叶节点数约定为 0。

约束：

• 节点数 $n\le 1000$
• 时间复杂度：$O(n)$
• 空间复杂度：$O(h)$，其中 $h$ 为树的高度（递归栈）

测试覆盖维度：测试用例除常规情况外还包含以下边界——

• 空树（应返回 0）
• 单节点（根自身就是叶子，应返回 1）
• 链状树（高度等于节点数，仅末端 1 个叶子）
• 满二叉树（叶子数 $=(n+1)/2$）
• 完全二叉树（叶子集中在最后两层）
• 接近上限 $n=1000$ 的大规模树（链状形态下递归栈深 ~1000 层）

请按以下要求作答：

(1) 给出算法的基本设计思想。

(2) 采用 C 语言描述算法，关键之处给出注释。

(3) 说明算法的时间复杂度与空间复杂度，并给出推导。

参考答案与详细解析

详细解析

思路分析

核心观察：叶节点的"局部特征"完全由当前节点决定——只看自身的两个孩子指针是否都为空，与其它任何节点无关。因此适合用分治递归或遍历计数两种思路求解。

解法 1：后序递归分治（最简洁，推荐）

把"求整棵树的叶子数"分解为三种情况：

• 空树（T == NULL）：叶子数 = 0
• 当前节点是叶子（lchild 与 rchild 都为 NULL）：叶子数 = 1
• 其他情况：叶子数 = 左子树叶子数 + 右子树叶子数

写成递归式：

$$f(T)=\{\begin{array}{ll}0,& T=\text{NULL}\\ 1,& T\ne \text{NULL}\wedge T\text{->lchild}=\text{NULL}\wedge T\text{->rchild}=\text{NULL}\\ f(T\text{->lchild})+f(T\text{->rchild}),& \text{otherwise}\end{array}$$

这就是后序遍历的"自然 reduce"——先求左右子树各自的叶子数，再合并到当前节点的子树总数。

解法 2：任意遍历 + 计数（用栈或队列迭代）

任何顺序遍历整棵树，每访问到一个节点就检查它是不是叶子，是则计数器 +1。常见有：

• 用栈做先序 / 后序的非递归遍历
• 用队列做层序遍历（BFS）

时间空间都是 $O(n)$，但额外开辟栈/队列存储节点指针；写法繁琐，常数也比递归大。

为什么解法 1 更优：

• 代码 5 行解决，无需显式数据结构
• 调用栈深 = 树高 $h$，对一般二叉树平均 $O(\log n)$
• 思路与"$n_0$、$n_1$、$n_2$ 计数"的数学结构完全同构，便于与本 KP 选择题套（如完全二叉树 $n_0$ 计算）建立认知桥梁

参考实现（C）

int countLeaves(BiTree T) {
    if (T == NULL) return 0;                                  /* 空树：无叶子 */
    if (T->lchild == NULL && T->rchild == NULL) return 1;     /* 当前节点是叶子 */
    return countLeaves(T->lchild) + countLeaves(T->rchild);   /* 分治合并 */
}

3 个 return 分支正好对应递归式三种情况，无冗余分支。

复杂度证明

时间复杂度 $T(n)=O(n)$：

每个节点恰被函数访问一次（进入函数体），在该次访问中做常数 $O(1)$ 工作（两次指针比较 + 一次加法或返回常量）。共 $n$ 个节点，故总时间为：

$$T(n)=n\cdot O(1)=O(n)$$

空间复杂度 $S(n)=O(h)$：

唯一的额外空间是递归调用栈。递归在节点 $u$ 进入时，栈中保存 $u$ 的所有祖先链；最深时栈深 = 从根到某节点的路径长度 = 树高 $h$。

• 一般二叉树：$h\in [\lceil {\log }_2(n+1)\rceil ,n]$
• 链状二叉树（极端最坏）：$h=n$，故空间 $O(n)$；OJ 题面声明 $n\le 1000$ 时，1 MB 默认栈空间足够（每帧 ~64 字节，1000 帧 ~64 KB）
• 完全二叉树：$h=\lfloor {\log }_{2}n\rfloor +1=O(\log n)$

综合表达：$S(n)=O(h)$。

易错点

1. 盲区 A：「叶子判定写成 lchild = NULL 或 rchild = NULL」

   一战考生最常见的错写——把"左孩子或右孩子为空"当成叶子判定（用 || 而不是 &&）。这把"度为 1 的节点"（只有一个孩子）也算成了叶子。

   错误推演：示例 1 的树 1 → (2, 3); 3 → (4, 5)，根 1 的左孩子 2 是真叶子（两子皆空），右孩子 3 是度 2 节点（有 4 和 5）。若用 ||，节点 1 自己的 lchild != NULL 但 rchild != NULL，不算叶子（这步对）；但若改成另一棵树 1 → 2 → NULL（节点 2 只有左孩子），|| 把 2 算成叶子（因 rchild 为空），与真值不符。

   正解共识：叶子的本质是"度为 0"——孩子数恰为 0。两个孩子指针同时为空才是 0 个孩子；任一为非空都至少是 1 个孩子。逻辑必须用 &&。

   元层共识：建立「度为 0 vs 度为 1 vs 度为 2」三类节点的判定网络，与 [[kp-binary-tree-basics-101]]「$n_0+n_1+n_2=n$ 三类节点和」共享同一计数本体。

2. 盲区 B：「忘了空树兜底，递归栈段错误」

   有同学先写"叶子判定"那个分支，忘了在最前面判 T == NULL。当递归走到叶子节点的孩子（即 NULL）时，函数体内的 T->lchild 解引用空指针 → 段错误。

   错误推演：把代码改成：

   int countLeaves(BiTree T) {
       if (T->lchild == NULL && T->rchild == NULL) return 1;  /* 忘了空树兜底 */
       return countLeaves(T->lchild) + countLeaves(T->rchild);
   }

   传入空树（T = NULL），第一行 T->lchild 立刻 segfault。

   正解共识：任何递归处理树/链表的函数，第一行都要兜底"传入空指针怎么办"——这是数据结构题面"空树视为合法"约定的固定打法。把空指针视为递归基（base case），优先级最高。

   元层共识：与 [[kp-singly-linked-list-101]]「head 为 NULL 兜底」、[[kp-bst-search]]「空树查找返回 NULL」共享同一红线——指针递归的第一行必须是空指针兜底。

3. 盲区 C：「把'叶子数'与'外部节点数'混为一谈」

   408 教辅有时讨论"扩充二叉树"——把每个 NULL 当作一个虚拟"外部节点"。在扩充二叉树里，外部节点数 = 内部叶子数 + 1（这是另一条恒等式）。考生若把扩充视角带进本题，可能算出 n_0 + 1 而非 n_0。

   错误推演：示例 1 的树有 3 个叶子（2 / 4 / 5）和 6 个 NULL 指针（2 的左、2 的右、4 的左、4 的右、5 的左、5 的右），把 NULL 当外部节点会算成 6 / 2 = 3——巧合恰好等于真值，但思路完全错。换更不对称的树（如示例 2 链状）就会偏离。

   正解共识：本题问的是"原二叉树中度为 0 的节点"，即真实存在于二叉链表里的那种节点；NULL 指针不是节点。判定标准只看节点自身的两个孩子指针是否都为空。

4. 盲区 D：「递归吞栈：1000 节点的链状栈深认知错误」

   一战考生看到题面 $n\le 1000$ 直觉认为"才一千个节点，递归不可能栈溢出"。但链状二叉树的高度等于节点数——1000 节点的全左链需要 1000 层递归栈。每帧约 32-64 字节（含返回地址 + 局部指针），1000 帧 ~64 KB，远小于默认 1 MB 栈，本题安全。

   错误推演：若题面把上限放大到 $n={10}^6$，链状树递归栈需 ~64 MB，远超默认栈，会 stack overflow。考生若误以为"递归永远 $O(\log n)$"会在更大规模题上栽跟头。

   正解共识：递归栈空间 = 递归深度 × 单帧大小。深度上界 = 树高 $h$，而 $h$ 在最坏情况下等于 $n$（链状形态）。本题 $n\le 1000$ 安全；若需在更大规模下保险，应改为迭代 + 显式栈 或 Morris 遍历（$O(1)$ 空间）。

   元层共识（复杂度认知错因）：与 [[kp-general-tree-101]]「兄弟链递归吞栈」、[[kp-bst-search]]「BST 退化为链表」共享同源——树形递归的空间是 $O(h)$ 不是 $O(\log n)$，$h$ 在最坏情况下等于 $n$。

综合题 3｜巩固题

难度：★★ · 分值：12 分

考点：二叉树基础（性质+存储）、二叉树、最大深度、后序遍历、递归、算法设计

二叉树结点定义如下（系统已提供）：

typedef struct TreeNode {
    int               val;
    struct TreeNode  *left;
    struct TreeNode  *right;
} TreeNode;

请设计算法，给定二叉树根指针 root，返回它的最大深度——从根结点到最远叶结点的最长路径上的结点数。空树的最大深度约定为 0，只有根结点的树最大深度为 1。

约束：

• 时间复杂度：$O(n)$
• 空间复杂度：$O(h)$，其中 $h$ 为树高（递归栈）

测试覆盖维度：空树（返回 0）、单结点（返回 1）、链状树（深度 = 结点数）、满二叉树、完全二叉树、左右极不平衡的树。

请按以下要求作答：

(1) 给出算法的基本设计思想。

(2) 采用 C 语言描述算法，关键之处给出注释。

(3) 说明算法的时间复杂度与空间复杂度，并给出推导。

参考答案与详细解析

详细解析

(1) 设计思想

一棵树的最大深度，等于「左子树最大深度」与「右子树最大深度」中较大者，再加上根结点自己这一层。这是一个天然的递归定义：

$$\text{depth}(root)=\{\begin{array}{ll}0,& root=\text{NULL}\\ max(\text{depth}(root\text{->left}),\text{depth}(root\text{->right}))+1,& \text{otherwise}\end{array}$$

先算出左右子树的深度、再组合出当前结点的答案，这正是后序遍历的顺序（先处理左右子树，再处理根）。这道题没有「暴力 vs 最优」的分差——访问每个结点一次就是 $O(n)$ 的下界，直白写法即最优，属「直观即满分」型。

(2) 参考实现（C）

int maxDepth(TreeNode* root) {
    if (root == NULL) return 0;                 /* 空树深度 0（递归基，必须最先） */
    int l = maxDepth(root->left);               /* 先算左子树深度 */
    int r = maxDepth(root->right);              /* 再算右子树深度 */
    return (l > r ? l : r) + 1;                 /* 较大者加一（后序合并） */
}

走一遍：根 1，左孩子 2（2 又挂左孩子 4），右孩子 3。递归到 4 时左右都空，返回 1；结点 2 左深 1、右深 0，取大加一返回 2；结点 3 返回 1；根 1 左深 2、右深 1，取大加一返回 3。

(3) 复杂度

时间 $O(n)$：每个结点恰被 maxDepth 访问一次，每次做常数工作（两次比较 + 一次取大加一），$T(n)=n\cdot O(1)=O(n)$。访问每个结点是判定深度的必需——少看一个结点，若它恰在最深路径上答案就错，故 $O(n)$ 是下界，无可优化。

空间 $O(h)$：唯一额外空间是递归栈，最深时栈中保存从根到某结点的路径，深度 = 树高 $h$。平衡树 $O(\log n)$，链状树最坏 $h=n$ 即 $O(n)$。

易错点

1. 空树返回 -1 或忘写递归基：root == NULL 必须返回 0，且是函数第一行；写成 -1 会让所有深度整体偏移，忘写则递归走到叶结点的空孩子时 root->left 解引用空指针崩溃。

2. 「加一」放错位置：必须先递归求出 l、r 再取较大值加一；若在递归前就加，逻辑与后序定义脱节。

3. 别画蛇添足：想维护全局最大深度变量、自顶向下传 depth，或改用 BFS 层序数层——都能算对且同为 $O(n)$，但后序返回值自底向上组合的写法不需要任何额外状态或数据结构，更短更稳，选它。

最终答案

• (1) 后序递归：空树深 0，非空结点深 = max(左深, 右深) + 1。
• (2) 见上 maxDepth。
• (3) 时间 $O(n)$，空间 $O(h)$（最坏链状 $O(n)$）。

综合题 4｜巩固题

难度：★★★ · 分值：12 分

考点：二叉树基础（性质+存储）、平衡二叉树、自底向上、剪枝、哨兵、递归、算法设计

二叉树结点定义如下（系统已提供）：

typedef struct TreeNode {
    int               val;
    struct TreeNode  *left;
    struct TreeNode  *right;
} TreeNode;

请设计算法判断给定二叉树是否为平衡二叉树——即树中每个结点的左右子树高度差的绝对值都不超过 1。平衡返回 1，否则返回 0；空树视为平衡。要求分析时间复杂度，并尽可能高效。

约束：

• 时间复杂度：期望 $O(n)$
• 空间复杂度：$O(h)$，其中 $h$ 为树高（递归栈）

测试覆盖维度：空树、单结点、满/完全二叉树（平衡）、链状树（不平衡）、仅在深处才失衡的树（考验剪枝与不重算）、左右子树高度差恰为 1 与恰为 2 的临界树。

请按以下要求作答：

(1) 给出算法的基本设计思想。

(2) 采用 C 语言描述算法，关键之处给出注释。

(3) 说明算法的时间复杂度与空间复杂度，并给出推导。

参考答案与详细解析

详细解析

(1) 设计思想

起步解：自顶向下（暴力，O(n²)）

最直接的想法：对每一个结点，分别求左子树高度 lh、右子树高度 rh，判 $|lh-rh|\le 1$；再对左右子树递归做同样检查。

int height(TreeNode* root) {
    if (root == NULL) return 0;
    int lh = height(root->left), rh = height(root->right);
    return (lh > rh ? lh : rh) + 1;
}
int isBalanced(TreeNode* root) {
    if (root == NULL) return 1;
    int lh = height(root->left), rh = height(root->right);
    if (lh - rh > 1 || lh - rh < -1) return 0;
    return isBalanced(root->left) && isBalanced(root->right);
}

这份解逻辑正确，能拿正确性分。但用「找浪费三问」审：有没有重算已知的东西？——有。 isBalanced 递归到子结点时会再次 height(子树)，而这段子树内部每个结点的高度，在上一层算 height(父) 时其实已经算过一次、算完就丢了。越靠近根的结点，其 height() 覆盖的子树越大，层层叠加，最坏退化到 $O(n^2)$。

最优解：自底向上一遍算完（O(n)）

对策：把「求高度」与「判平衡」合并进同一次递归。每个结点的高度在算出来的那一刻就顺带完成本结点的平衡判断，通过返回值上传，父结点不再重新算。用 -1 作哨兵表示「本子树或其某个子树已不平衡」，一旦出现就沿调用链一路上传、每层直接放弃后续计算（左子树已 -1 就不必再算右子树——剪枝）。这样每个结点高度只被计算一次，达到 $O(n)$，也是本题的复杂度下界。

(2) 参考实现（C）

static int checkHeight(TreeNode* root) {
    if (root == NULL) return 0;                       /* 空树高 0 */
    int lh = checkHeight(root->left);
    if (lh == -1) return -1;                          /* 左子树已不平衡，剪枝上传 */
    int rh = checkHeight(root->right);
    if (rh == -1) return -1;                          /* 右子树已不平衡，剪枝上传 */
    if (lh - rh > 1 || lh - rh < -1) return -1;       /* 当前结点不平衡 */
    return (lh > rh ? lh : rh) + 1;                   /* 平衡：正常返回高度 */
}

int isBalanced(TreeNode* root) {
    return checkHeight(root) != -1;
}

(3) 复杂度

时间：最优解 $O(n)$——checkHeight 对每结点只调用一次、常数工作。对照暴力自顶向下，height() 被每个结点各触发一次、各自遍历整棵子树，最坏 $O(n^2)$；差距来自高度信息的反复重算，自底向上把它彻底消除。判平衡至少要看每个结点一遍，$O(n)$ 是下界。

空间 $O(h)$：递归栈深 = 树高 $h$；平衡 $O(\log n)$、链状最坏 $O(n)$。

易错点

1. 停在自顶向下的 O(n²)：写对暴力解只拿正确性分；题目要求「尽可能高效」，$O(n^2)$ 拿不到最优性分。要点是识别「高度被反复重算」这一浪费，并合并成自底向上一遍。

2. -1 哨兵未一路上传 / 未剪枝：发现不平衡后要立刻返回 -1 且每层都直接放弃后续；if (lh == -1) return -1; 必须在算右子树之前，否则白算右子树。

3. 空树/边界：checkHeight(NULL) 返回 0，isBalanced(NULL) 返回 1。

4. 动态场景的进一步优化：若是频繁插删的 AVL 树，应给结点缓存 height 字段、沿路径增量更新，单次维护 $O(\log n)$——本题静态判定用 $O(n)$ 即可，不必上缓存。

最终答案

• (1) 自底向上：把求高与判平衡合并为一次递归，-1 哨兵剪枝；对照自顶向下暴力 $O(n^2)$。
• (2) 见上 checkHeight / isBalanced。
• (3) 时间 $O(n)$（暴力 $O(n^2)$），空间 $O(h)$。

综合题 5｜巩固题

难度：★★ · 分值：12 分

考点：二叉树基础（性质+存储）、对称二叉树、镜像、交叉配对、递归、算法设计

二叉树结点定义如下（系统已提供）：

typedef struct TreeNode {
    int               val;
    struct TreeNode  *left;
    struct TreeNode  *right;
} TreeNode;

请设计算法，判断给定二叉树是否关于根结点左右对称——沿根结点画一条竖线对折，左右两半应完全重合：不仅结构对称，每个对称位置上的结点值也要相等。对称返回 1，否则返回 0；空树视为对称。

例如根 1、左孩子 2(左 3 右 4)、右孩子 2(左 4 右 3) 的树对称；而根 1、左孩子 2(左空 右 3)、右孩子 2(左空 右 3) 不对称（两个 3 都长在右边，折过去对不上）。

约束：时间 $O(n)$，空间 $O(h)$（$h$ 为树高，递归栈）。

测试覆盖维度：空树、单结点、结构对称但值不对称、值对称但结构不对称（一空一非空）、链状树、多层完全对称的树。

请按以下要求作答：

(1) 给出算法的基本设计思想。

(2) 采用 C 语言描述算法，关键之处给出注释。

(3) 说明算法的时间复杂度与空间复杂度，并给出推导。

参考答案与详细解析

详细解析

(1) 设计思想

「对称」这个词本身在暗示做法：一棵树对称 $⟺$ 它的左子树和右子树互为镜像。互为镜像的关键是交叉相等：左子树的左孩子对上右子树的右孩子、左子树的右孩子对上右子树的左孩子——这跟「两棵子树长得一样」不是一回事。于是设一个专判「两棵子树是否互为镜像」的函数 isMirror(l, r)，同步递归地把这个交叉关系一路核对下去。属「直观即满分」型——遍历每个结点一次就是 $O(n)$ 下界，无优化空间。

(2) 参考实现（C）

static int isMirror(TreeNode* l, TreeNode* r) {
    if (l == NULL && r == NULL) return 1;   /* 都空：这一层对称 */
    if (l == NULL || r == NULL) return 0;   /* 一空一非空：不对称 */
    if (l->val != r->val) return 0;         /* 值不等：不对称 */
    return isMirror(l->left, r->right)      /* 交叉：l 左对 r 右 */
        && isMirror(l->right, r->left);     /* 交叉：l 右对 r 左 */
}

int isSymmetric(TreeNode* root) {
    if (root == NULL) return 1;             /* 空树视为对称 */
    return isMirror(root->left, root->right);
}

走一遍对称树（根 1，左 2(3,4)、右 2(4,3)）：isMirror(2,2) 值相等，交叉递归 isMirror(3,3)（左的左对右的右）与 isMirror(4,4)（左的右对右的左），叶对叶、值相等，全返回 1。再走不对称例：isMirror(2,2) 值相等，交叉递归到 isMirror(NULL, 3)——一空一非空，返回 0。

(3) 复杂度

时间 $O(n)$：每个结点作为 l 或 r 恰被访问一次、做常数工作。判对称至少要看每个结点一遍（少看一个可能漏掉一处不对称），$O(n)$ 是下界。

空间 $O(h)$：递归栈深 = 树高 $h$；平衡 $O(\log n)$、链状最坏 $O(n)$。

易错点

1. 交叉写成并排：把 isMirror(l->left, r->right) 写成 isMirror(l->left, r->left)——那是判「结构相同」，不是「互为镜像」。对折后左边的左孩子应落到右边的右孩子那侧，方向一旦记反就全错。

2. 空指针判断顺序：必须先判两者都空、再判一空一非空、最后才取 val；漏第一条直接比 val 会崩。

3. 空树：isSymmetric(NULL) 返回 1。

4. 别画蛇添足：不必序列化成字符串再比、也不必层序逐层判回文——递归交叉配对已一遍到位。

最终答案

• (1) 树对称 ⟺ 左右子树互为镜像；isMirror 交叉递归。
• (2) 见上 isMirror / isSymmetric。
• (3) 时间 $O(n)$，空间 $O(h)$。

完成清单

• 20 道选择题均已独立作答，错题能说明其余选项为何不成立；
• 5 道综合题均已独立完成，并在展开解析前写出推导或算法；
• 能把本组题目涉及的关键性质、遍历顺序或算法复杂度说清楚；
• 已记录仍需回到教材复习的知识点。

复盘

• 哪道题最容易因遍历顺序、层次口径或结构关系判断失误？
• 我能否不用背答案，重新画树或写出访问过程？
• 如果题目改变一个条件，原结论是否仍成立？