Code59 零基础 · 树 · 28—41

2026-09-14 · 零基础讲解 · 先读题目与条件，再看示例和逐步讲解

先读 第 0 课，再按每题“完整题干与条件 → 输入输出示例 → 人话讲解与状态推演 → 完整函数与逐句说明 → 自测”学习。题干整理和教学补充分别标注，原速查内容放在每题最后。

本篇对应全书第 28—41 题。n 为实际结点数，h 为树高。高度按层数计，空树高 0、只有根的树高 1；WPL 的深度另按边数计，根深度 0。递归函数先读“传入什么、返回什么”，不要一开始就展开所有调用。题意为转述，样例为本次补充，每题直接附完整函数，同时保留回源链接。

返回总目录

读代码前：编译环境与类型

本章展示的是完整函数，不是每题各有一个 main 的独立程序。练习编译一题时，将所需类型、辅助函数与题目函数放在同一份学习用 C 文件里，再添加调用它的 main；第 0 课给了最小程序例子。常用标准头文件如下（它们提供打印、分配空间、真假类型、整数上限）：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#define MAXSIZE 50

以下是本章使用的类型定义，不是要执行的解题步骤。字段含义见第 0 课；不要把不同章节重复的同名类型在同一文件中再定义多次。

typedef struct BTNode {
    char data;
    struct BTNode *lchild;
    struct BTNode *rchild;
} BTNode, *BiTree;

28｜判断正则二叉树（本章第 1 题）

题目与要求

题目（依据原题整理）：判断给定二叉树是否为正则二叉树。本题把“每个结点的度均为 0 或 2”的二叉树称为正则二叉树。

已知条件：输入二叉链表的根指针；结点的“度”就是它的孩子个数，空孩子用 NULL 表示。

需要得到：若每个结点要么没有孩子、要么同时有左右两个孩子，则返回真；只要有一个结点恰好只有一个孩子，就返回假。

输入 → 输出示例（教学补充）：根 A 有左孩子 B 和右孩子 C，B、C 都无孩子 → 真；若 A 只有左孩子 B → 假。

约定与提醒（教学补充）：正则树不要求所有叶子在同一层，也不等同于第 37 题的满二叉树。本函数把空树视为满足条件，这是递归中的约定。

题干回源：Code59 PDF 第 15 页；回源 · PDF 第 15 页 · b_15_7 。

1. 正则二叉树，只检查有没有“独生孩子”

树结点的度是它直接拥有几个孩子，不是它有多少后代。正则二叉树要求每个结点要么没孩子，要么两个孩子，不能只有左孩子或只有右孩子。

输入是一棵树的根地址，输出 true/false。root 是本次正在检查的那棵子树的根；递归到孩子后，新的 root 会变成那个孩子，不是永远指整树最上面。

2. 四种情况先列出来，再读递归

左孩子存在吗	右孩子存在吗	当前结点合格吗
否	否	合格，是叶子
是	否	不合格，只有一个孩子
否	是	不合格，只有一个孩子
是	是	当前合格，还要继续检查两边后代

例子：A 有 B、C，B 无孩子，C 只有 D。检查 A：两个孩子都有，暂合格；检查 B：两个都无，合格；检查 C：只有一个，返回 false；A 收到右边失败，整树判 false。不能只检查 A 后就结束。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

bool isRegularBinaryTree(BiTree root) {
    if (root == NULL)
        return true;

    bool hasLeft = root->lchild != NULL;
    bool hasRight = root->rchild != NULL;
    if (hasLeft != hasRight)
        return false;

    return isRegularBinaryTree(root->lchild)
        && isRegularBinaryTree(root->rchild);
}

root 为 NULL 表示没有结点，自然也没有不合格结点，返回 true。hasLeft=root->lchild!=NULL 把“有左孩子吗”的答案存为一个布尔变量，hasRight 同理。

若两个布尔值不同，正好对应表里中间两行，return false。若相同，当前结点没问题；最后分别递归检查左、右子树，用 && 要求两边都合格。左边已失败时，短路可不再检查右边，因为最终答案已确定。

4. 自己试一下

只有一个根：合格。根带两个叶子：合格。根带一个叶子：不合格。根有两个孩子，其中一边还有两孩子，另一边是叶子：仍可能正则，但不是每层都满；不要在这里加“左右高度必须相等”，那会变成另一个题。

学懂后回看：结论、复杂度与回源

题意与结论：本题“正则”指每个结点的度只能为 0 或 2，即没有只带一个孩子的结点。逐结点检查左右孩子是否同时存在，再递归检查两棵子树。

思路推导：整棵树满足性质，等价于“根没有单孩子，并且左右子树各自满足”。这就是递归拆解：当前调用只负责当前根，再把同样问题交给孩子。

走一遍：A 有孩子 B、C，B 是叶子，C 有两个叶孩子 D、E。A、C 的度为 2，B、D、E 的度为 0，返回 true。若删掉 E，则 C 只剩 D，C 这一层返回 false，向上传到 A，整树不正则。

代码抓手与正确性：(lchild==NULL)!=(rchild==NULL) 表示两边存在性不同，立即失败。空子树返回 true，代表它没有违反条件的结点；否则返回左右子树判断的逻辑与。用结构归纳可知每个结点都被检查到。

复杂度与易错点：时间 O(n)，递归栈 O(h)。正则不等于王道口径的满二叉树：上述正则例子的叶子不在同一层，因此不是满树。不要因为某些英文资料把另一概念叫 full，就改掉本题定义。

回源：PDF 第 15 页；回源 · PDF 第 15 页 · b_15_7；PDF 第 15 页 · b_15_8；PDF 第 15 页 · b_15_9；PDF 第 15 页 · b_15_10 。正式代码

29｜表达式树转中缀表达式（本章第 2 题，2017）

题目与要求

题目（依据原题整理）：给定一棵用二叉链表存储的二叉表达式树，设计一个算法，把它转化为等价的中缀表达式，并用括号保证输出表达式的运算顺序与原树一致。

已知条件：叶子表示操作数，内部结点表示二元运算符；左、右子树分别表示左、右操作数。本章示例每个结点存一个字符。

需要得到：一个可以从左到右阅读的表达式字符串，而不是先序序列或仅列出运算符。

输入 → 输出示例（教学补充）：根为 *，左孩子是 +（其左右叶子为 a、b），右叶子为 c → 输出 (a+b)*c。

约定与提醒（教学补充）：示例树由文字完整定义，是新增教学例子；原资料所说的视频配图未附在该题文本中，不把示例冒充原图。输出不要求括号最少，但不能因漏括号把乘法和加法的先后改掉。

题干回源：Code59 PDF 第 15 页；回源 · PDF 第 15 页 · b_15_2；PDF 第 15 页 · b_15_5 。

1. 树上的括号关系，不能在输出时丢掉

设根是 *，左孩子是 +，这个 + 的两个叶子为 a、b；根的右孩子是 c。它表达“先算 a+b，再乘 c”，输出必须是 (a+b)*c，不能是 a+b*c。

叶子是一个操作数，内部结点是运算符。depth 表示离整树根有几条边，第一次传 0。这个函数只打印表达式，不计算数值。

2. 按打印发生的先后看输出字符串

到哪里、正在做什么	追加的字符	目前已打印
进入根 *，depth=0，不加外括号	无	空
进入左子树 +，非根且为运算符	(	(
处理左叶 a	a	(a
回到 +，打印自己	+	(a+
处理右叶 b，回到 +，闭括号	b)	(a+b)
回根打印 *，再右叶 c	*c	(a+b)*c

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

void printInfix(BiTree root, int depth) {
    if (root == NULL)
        return;

    bool isOperator = root->lchild != NULL || root->rchild != NULL;
    if (isOperator && depth > 0)
        printf("(");

    printInfix(root->lchild, depth + 1);
    printf("%c", root->data);
    printInfix(root->rchild, depth + 1);

    if (isOperator && depth > 0)
        printf(")");
}

空 root 直接 return，不打印。isOperator 用“至少有一个孩子”判断当前是否内部结点；在合法二元表达式树中，运算符有两个孩子。只有 isOperator 为真并且 depth>0，才先 printf 左括号。

中间三句按“递归左子树→打印自己→递归右子树”执行；递归传 depth+1，告诉下一层比自己深一层。最后用同一条件打印右括号，包住刚完成的整个子表达式。%c 表示按字符打印 data，不是按整数编码打印。

4. 自己试，括号为什么必需？

根为 -，左叶 a，右子树为 b-c，正确输出 a-(b-c)。若去掉括号，a-b-c 通常解释为 (a-b)-c，结果可能不同，例如 a=8、b=5、c=2，分别为 5 和 1。该代码保留足够括号保证等价，不追求“括号最少”。

学懂后回看：结论、复杂度与回源

题意与结论：中序遍历给出“左表达式、运算符、右表达式”，但还必须用括号保护子树的运算次序。除整树根外，对每棵非叶子子树加括号。

思路推导：表达式树中的父子关系记录运算优先级。只输出中序而不加括号，可能让读者按普通运算优先级解释成另一棵树；因此要把非根内部子树包成整体。

走一遍：根为 *，左孩子是 +（叶 a、b），右孩子 c。左子树进入时先输出 (，依次输出 a+b，退出时输出 )；随后输出根的 * 和 c，结果 (a+b)*c。若只中序输出 a+b*c，含义就错了。

代码抓手与正确性：depth 从 0 开始；代码用 isOperator 表示存在孩子的非叶结点，条件 isOperator && depth>0 控制括号。左括号在递归左子树之前打印，右括号在递归右子树之后打印。每个复合子表达式被整体保护，所以不会被外面的运算符错误拆开。

复杂度与易错点：时间 O(n)，栈 O(h)。这套写法保证等价，不追求括号数量绝对最少。叶子通常不加括号，整棵表达式最外层括号也可省。默认合法二元表达式树；一元负号或函数调用需额外定义。

回源：PDF 第 15 页；回源 · PDF 第 15 页 · b_15_2；PDF 第 15 页 · b_15_5 。正式代码

30｜表达式树求值（本章第 3 题）

题目与要求

题目（依据原题整理）：表达式 (a-(b+c))*(d/e) 存储在二叉表达式树中，求四则运算后的结果。一般任务是：给定表达式树和操作数的数值，计算整棵树表示的表达式值。

已知条件：运算符结点有左右两个孩子，叶子表示操作数。原题文本没有给出 a、b、c、d、e 的具体数值，因此不能直接得出唯一的数值答案。

需要得到：在操作数已知时得到表达式的计算结果，减法与除法必须区分左右操作数。

输入 → 输出示例（教学补充）：取 a=8、b=2、c=3、d=6、e=2，树表示 (8-(2+3))*(6/2) → 结果为 9。

约定与提醒（教学补充）：下面锁定校订函数只处理叶子为单个数字字符 '0' 到 '9' 的树，示例也按此构造；若保留变量字母，必须另外提供变量取值表。该函数采用整数运算，除法截去小数部分，例如 7/2 得 3；它不是通用实数表达式求值器。要求表达式合法、除数不为 0，且整数运算不溢出。

题干回源：Code59 PDF 第 15 页；回源 · PDF 第 15 页 · b_15_3；PDF 第 15 页 · b_15_6 。数值例子不是原题给定数值。

1. 和上一题不同，这次需要交回数字

输入是一棵合法的数字表达式树，例如 (8-(2+1))*(6/3)。输出整数 10。正式代码只把叶子当 '0' 到 '9' 的单个数字字符；多位数 12 不能塞进一个 char 当作字符串直接算。

left、right 是两个子表达式算完后交回的整数，不是左右孩子的地址。若孩子没算完，父运算符只能等。

2. 先算哪个？父任务在哪里暂停？

当前小任务	等孩子交回什么	本层计算	交回谁
2+1 那个 +	左=2，右=1	3	交回上一层 -
8-(2+1) 那个 -	左=8，右=3	5	交回最外层 *
6/3 那个 /	左=6，右=3	2	交回最外层 *
最外层 *	左=5，右=2	10	交回调用者

这就是“后序”：先处理左右子树，最后处理当前根。不是说函数从代码最后一行开始执行。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

int evaluateExpressionTree(BiTree root) {
    if (root->lchild == NULL && root->rchild == NULL)
        return root->data - '0';

    int left = evaluateExpressionTree(root->lchild);
    int right = evaluateExpressionTree(root->rchild);

    switch (root->data) {
        case '+': return left + right;
        case '-': return left - right;
        case '*': return left * right;
        case '/': return left / right;
        default:  return 0;  // 实际程序中应报告非法运算符
    }
}

如果左右孩子都空，说明当前是叶子，直接用 data-'0' 转数。例如字符 '8' 与 '0' 的编码相差 8，所以结果是数值 8，而不是字符编码本身。

内部结点先递归取得左结果，再取得右结果。switch 看当前 data 属于哪个运算符；case '+' 返回 left+right，其他三项同理，减与除必须保留左右次序。每个 case 的 return 都结束本次函数，所以不需要再写 break 防止进入下一项。

default 是非法符号的兜底，正式片段暂返回 0，但真实学习时不能把“错误也得到 0”当作可靠计算；应保证输入合法或增加错误报告。函数也没有处理 root 为 NULL、除零等非法情况。

4. 自己试一下

(9-3)/2：减法子树先交回 6，根再 6/2 得 3。若右左颠倒，会变成 2/6，整数结果 0。7/2 在当前整数实现中是 3，不是 3.5；符号 a 若未给值，现有信息不足以算出确定数字。

学懂后回看：结论、复杂度与回源

题意与结论：先求左右子表达式，再按根运算符计算，即后序递归。正式代码的叶子按单个数字字符 '0'..'9' 处理。

思路推导：运算符自身没有最终数值，要等两个操作数算出来。例如根是乘号，只有知道左右子树的值，才能做最后一次乘法。因此递归必须先返回孩子的结果。

走一遍：表达式 (8-(2+1))*(6/3)。最底层先算 2+1=3 与 6/3=2；再算 8-3=5；根算 5*2=10。不是从左到右机械扫描符号。

代码抓手与正确性：叶子用 root->data-'0' 把字符转成数值；内部结点先把左右子树结果存为 left、right，再在 switch 中运算。减法与除法不能颠倒左右参数。以叶子值为基础、按运算定义合成父节点值，递归结果就等于整棵表达式的值。

复杂度与易错点：时间 O(n)，栈 O(h)。原题文字出现 a、b 等变量时，必须知道变量取值；现有信息不足时不能编造结果。本例是专为解释代码补充的数字表达式。正式实现为整数计算，7/2 为 3；多位数、变量查表、除零、溢出和非法运算符需另加处理，不能说这段代码已覆盖。

回源：PDF 第 15 页；回源 · PDF 第 15 页 · b_15_3；PDF 第 15 页 · b_15_6 。正式代码

31｜输出根到所有叶子的路径（本章第 4 题）

题目与要求

题目（依据原题整理）：给定一棵二叉树，编写算法，输出从根结点到每个叶子结点的路径。

已知条件：输入二叉链表根指针；叶子是左右孩子都不存在的结点。

需要得到：每个叶子对应一条完整路径，方向为根到叶，路径中包括起点根和终点叶子。

输入 → 输出示例（教学补充）：A 的左右孩子为 B、C，B 的左右孩子为 D、E，C、D、E 都是叶子 → 输出 A→B→D、A→B→E、A→C 三条路径。

约定与提醒（教学补充）：不能把一次遍历的全部结点拼成一行来代替路径；下面先输出左边再输出右边。示例箭头表示路径方向，代码可按字符与换行打印，不必真的打印箭头。

题干回源：Code59 PDF 第 16 页；回源 · PDF 第 16 页 · b_16_1；PDF 第 16 页 · b_16_0 。

1. 路径是一条从根走到某个叶子的完整路线

树为 A 的孩子 B、C，B 的孩子 D、E，C 为叶。应输出三行：A→B→D，A→B→E，A→C。不能把所有访问到的字符拼成一行 ABD EC 来代替路径。

path 是一张当前路线便签；depth 在进入函数时是当前结点应写的下标，执行 depth++ 后变成路线有效长度。递归参数传的是数值副本，每层有自己的 depth。

2. 旧路径尾巴不清空，为什么也不会串？

当前调用	写到哪个格子	本层 depth++ 后	是否输出
A，传入 depth=0	path[0]=A	1	非叶，不输出
B，传入 1	path[1]=B	2	非叶
D，传入 2	path[2]=D	3	输出前三格 A B D
E，重新从 B 传入 2	path[2]=E	3	输出前三格 A B E
C，重新从 A 传入 1	path[1]=C	2	只输出前两格 A C

最后 path[2] 可能仍是 E，但有效长度只有 2，所以不会打印它。便签有旧字不等于旧字还属于当前路线。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

void printRootToLeafPaths(BiTree root, char path[], int depth) {
    if (root == NULL)
        return;

    path[depth] = root->data;
    depth++;

    if (root->lchild == NULL && root->rchild == NULL) {
        for (int i = 0; i < depth; i++)
            printf("%c%s", path[i], i + 1 == depth ? "\n" : " -> ");
        return;
    }

    printRootToLeafPaths(root->lchild, path, depth);
    printRootToLeafPaths(root->rchild, path, depth);
}

空结点直接返回。先写 path[depth]，再让 depth 增一，这两句不能反过来，否则首格留空、整条路径错位。判断两孩子都空时，for 的 i<depth 输出恰好有效的那些格子。

printf 的 %c%s 先打印字符，再打印一个字符串：若 i+1==depth 说明是最后一个字符，选换行；否则选箭头字符串。打印叶路径后 return，不再往空孩子递归。

非叶则先递归左边，再右边，传入本层已经加一的 depth。孩子把自己的 depth 加得更多，也不会改掉父层保存的 depth，所以从 B 返回 A 时，A 仍记得自己路线长度为 1。

4. 自己试一下

只有根 X，开始 path[0]=X、depth=1，两个孩子都空，打印一行 X。若打印数组全部容量，旧路径内容会混进来；只打印有效前缀才正确。统计总耗时还要算输出的所有字符，不能把打印很长路径当成免费。

学懂后回看：结论、复杂度与回源

题意与结论：DFS 时把当前沿途结点存进 path，遇到叶子就输出有效路径。depth 既表示深度，也给出当前结点应写的位置。

思路推导：只打印遍历次序会把不同分支混在一起。路径数组保存的是“这一次递归调用链走过的祖先”，每下探一层，就把新结点追加到对应下标。

走一遍：A 的孩子为 B、C，B 的孩子为 D、E，C 为叶。走到 D 时 path=[A,B,D]，输出 A→B→D；回到 B 再走 E 时把 path[2] 覆盖为 E，输出 A→B→E；回到 A 走 C，path[1]=C，只输出前两个位置 A→C，旧的 E 不在有效路径内。

代码抓手与正确性：当前结点先写 path[depth]，再 depth++，使 depth 变成当前有效路径长度；递归孩子传入这个已增加的 depth；只有左右孩子都空才输出下标 0..depth-1。depth 按值传递，返回上一层时自然恢复上一层长度，无须显式清空数组。

复杂度与易错点：访问树本身 O(n)，加上输出后为 O(n+P)，P 是所有输出路径长度之和；不能无条件把打印全算成 O(n)。工作空间 O(h)，路径数组容量需足够。叶子不是“缺一个孩子”，只有两个孩子都没有才是叶子。

回源：PDF 第 16 页；回源 · PDF 第 16 页 · b_16_1；PDF 第 16 页 · b_16_0；PDF 第 16 页 · b_16_6 。正式代码

32｜设置 parent 并输出每个结点到根的路径（本章第 5 题）

题目与要求

题目（依据原题整理）：为二叉链表的每个结点增加一个指向双亲结点的 parent 指针，并输出所有结点到根结点的路径。

已知条件：输入二叉树的左右孩子链接；双亲就是直接连接在该结点上方的父结点，根没有双亲。

需要得到：先正确设置所有 parent 指针，再从每一个结点分别向根输出一条路径。

输入 → 输出示例（教学补充）：A 为根，左孩子 B，B 的左孩子 D → 设置 A.parent=NULL、B.parent=A、D.parent=B，输出 A、B→A、D→B→A。

约定与提醒（教学补充）：本题输出所有结点的路径，不只是叶子的；方向也与第 31 题相反。未经初始化的 parent 不能直接拿来向上行走。

题干回源：Code59 PDF 第 16 页；回源 · PDF 第 16 页 · b_16_2 。

1. 给每个结点加一张“父亲住址卡”

普通二叉链表只知道孩子在哪里，不知道父结点在哪里。新增 parent 字段，先把所有父地址设置好，再从每个结点沿 parent 向上输出。

树 A 带 B、C，B 带 D。应能输出 A；B→A；D→B→A；C→A。内部结点也要输出，不只叶子。parent 是地址，不是父结点的 data。

2. 先建立地址关系，再沿关系走

设置时的调用	本次 root	参数 parent	写入的字段
setParents(A,NULL)	A	NULL	A.parent=NULL
左递归	B	A	B.parent=A
B 的左递归	D	B	D.parent=B
回到 A 后右递归	C	A	C.parent=A

打印 D 的路径时，临时 p 从 D→B→A→NULL，依次打印 D、B、A；走到 NULL 后停，不把 NULL 当成一个结点打印。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

typedef struct ParentBTNode {
    char data;
    struct ParentBTNode *lchild;
    struct ParentBTNode *rchild;
    struct ParentBTNode *parent;
} ParentBTNode, *ParentBiTree;

void setParents(ParentBiTree root, ParentBiTree parent) {
    if (root == NULL)
        return;

    root->parent = parent;
    setParents(root->lchild, root);
    setParents(root->rchild, root);
}

void printAllPathsToRoot(ParentBiTree root) {
    if (root == NULL)
        return;

    for (ParentBiTree p = root; p != NULL; p = p->parent)
        printf("%c%s", p->data, p->parent == NULL ? "\n" : " -> ");

    printAllPathsToRoot(root->lchild);
    printAllPathsToRoot(root->rchild);
}

结构体新增 *parent，其余 lchild/rchild 仍是孩子地址。类型别名 ParentBiTree 表示指向这种新结点的指针，不要与没有 parent 字段的旧结点混用。

设置函数空树返回；root->parent=parent 把调用者告诉自己的父地址记好；下一层调用传 (root->lchild,root)，含义是“去给左孩子设置父亲，父亲就是当前 root”，右边同理。

打印函数每到一个 root，先用 for 沿父指针打印这一个 root 的整条向上路径；然后再递归去处理左右子树中的其他起点。for 里改的是临时 p，不修改任何 parent 字段；遇根 parent 为 NULL 时打印换行。

4. 自己试，为什么要调用两阶段？

先调用 setParents(root,NULL)，再 printAllPathsToRoot(root)。若反过来，parent 还可能是未初始化地址，会乱走。练习根 A 只有孩子 B：设置 A.parent=NULL、B.parent=A；输出 A 和 B→A，共两条，不是只输出 B→A。

学懂后回看：结论、复杂度与回源

题意与结论：先遍历设置每个结点的父指针，再从每个结点出发沿 parent 向上打印，直到 NULL。与上一题相比，方向相反，而且不是只处理叶子。

思路推导：普通二叉链表只能向下走。若需要经常向上追祖先，把父结点地址预先存好即可；建立阶段把“当前根是谁的孩子”当作递归参数传入。

走一遍：A 有孩子 B、C，B 有左孩子 D。设置 A.parent=NULL，B.parent=A，C.parent=A，D.parent=B。遍历到 D 时输出 D→B→A；到 B 时输出 B→A；到 A 时输出 A。不要漏掉内部结点自己的路径。

代码抓手与正确性：调用 setParents(root,NULL)；对子树调用传入当前 root 作为 parent。输出某条路径时使用临时指针不断 p=p->parent，不要把树中保存的 parent 改掉。每次上移恰好经过真实父边，所以最终到根。

复杂度与易错点：建立父指针 O(n)；全路径输出总时间与所有结点深度之和相关，最坏 O(nh)，链状树为 O(n²)，不能合称 O(n)。每结点新增 parent 字段占总计 O(n) 存储；遍历工作栈为 O(h)。根 parent 必须置空，否则可能沿未初始化地址乱走。

回源：PDF 第 16 页；回源 · PDF 第 16 页 · b_16_2 。正式代码

33｜最近公共祖先 LCA（本章第 6 题）

题目与要求

题目（依据原题整理）：给定二叉树中的两个结点 p、q，找到它们的最近公共祖先。并考虑二叉树采用顺序存储时怎样完成同一任务。

已知条件：两个目标结点均确实存在于同一棵树中；本题允许一个结点作为它自己的祖先。

需要得到：同时是 p、q 祖先的结点中，距离根最远、层次最深的那个。下面两个函数都返回结点指针；顺序版本先求祖先的下标，再返回该位置保存的结点指针。

输入 → 输出示例（教学补充）：A 的左孩子 B，B 的左右孩子为 D、E → D 与 E 的最近公共祖先是 B；B 与 D 的最近公共祖先也是 B。

约定与提醒（教学补充）：“最近”不是结点值最接近。顺序版本用数组 nodes[] 按树位置保存结点指针，根下标为 0，非根位置 i 的父下标为 (i-1)/2（整数除法）；不能套用根下标为 1 的公式。

题干回源：Code59 PDF 第 16 页；回源 · PDF 第 16 页 · b_16_4；PDF 第 16 页 · b_16_5；PDF 第 16 页 · b_16_7 。

1. “最近”是离两个目标都最近的共同祖先

设 A 的孩子为 B、C，B 的孩子为 D、E。D 与 E 的共同祖先有 B、A，最近的是更低的 B。B 与 D 的答案是 B，本题允许结点是自己的祖先。

递归返回的地址不是“数值最小结点”，而是“这棵子树找到的目标或已经确定的共同祖先”。题设默认 p、q 都真正在树里。

2. 两边的返回值怎么在 B 处汇合

调用位置	左边交回	右边交回	本层交回
D 本身	不必继续查	D 正好就是目标 p	D
E 本身	不必继续查	E 正好就是目标 q	E
B	D	E	两边都有目标，交回 B
C 子树	NULL	NULL	NULL
A	B	NULL	只有左边有结果，原样交回 B

如果在 A 处收到左边 B 后又返回 A，会把已经找到的更近答案改成更远答案，所以只能原样上传。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

BiTree lowestCommonAncestor(BiTree root, BiTree p, BiTree q) {
    if (root == NULL || root == p || root == q)
        return root;

    BiTree left = lowestCommonAncestor(root->lchild, p, q);
    BiTree right = lowestCommonAncestor(root->rchild, p, q);

    if (left != NULL && right != NULL)
        return root;
    return left != NULL ? left : right;
}

代码段 2

↑ 回到本题题目

BiTree lowestCommonAncestorInArray(BiTree nodes[], int i, int j) {
    while (i != j) {
        if (i > j)
            i = (i - 1) / 2;
        else
            j = (j - 1) / 2;
    }
    return nodes[i];
}

第一段代码：root 为空，或它正好等于 p、q 中某个地址，直接返回 root。否则分别递归，结果存到 left、right。两者都非空，目标分居两支，return root；否则三目表达式选唯一非空的一边，若两边都空自然也返回 NULL。

第二段是顺序存储版本，思想不同：i、j 是两个位置下标，父位置为 (i-1)/2。每次把较大下标往父结点抬，直到相等。例如 3、4：先 4→1，再 3→1，两者相遇。最后交回 nodes[i] 保存的结点地址，不只是数字 i。

4. 自己试与前提提醒

找 D、C，答案为 A；找 D、D，答案为 D。若 q 根本不在树中，链式函数可能仅返回 p，不能宣称 p 就是合法共同祖先，因此“不存在目标”的输入需额外验证。相同 data 不保证同一个结点，判断仍用地址。

学懂后回看：结论、复杂度与回源

题意与结论：找同时包含 p、q 的最深祖先，允许结点是自己的祖先。链式树用递归向上返回“在哪一边找到目标”；顺序存储按父下标向上靠拢。

思路推导（链式）：空树返回 NULL；根正好是 p 或 q 就返回根；否则分别查左右。两边都非空，说明目标分居两侧，当前根就是首次汇合点；仅一边非空，就把那边结果继续向上传。

走一遍：A 的孩子 B、C，B 的孩子 D、E。找 D 与 E：D、E 分别向 B 返回自己，B 两边都有结果，返回 B；A 只有左边返回 B，因此最终答案仍为 B。找 B 与 D 时，B 本身就是答案。

代码抓手与正确性：比较的是结点地址 root==p，不是 data。链式算法假设 p、q 都存在；若只有一个存在，原函数可能直接返回那一个，不能据此断言找到了合法 LCA。需要一般接口时，额外验证两目标存在。

顺序存储走一遍：0 起始下标的父结点为 (i-1)/2。找下标 3、4：先把较大的 4 上移到 1，再把 3 上移到 1，相遇即答案 1。较大下标不可能是较小下标的祖先，所以可安全上移较大者。根 0 不再向上求父。

复杂度与易错点：链式时间 O(n)、栈 O(h)；顺序存储时间 O(h)、空间 O(1)。顺序下标必须对应真实存在结点，不能给空槽。不是比较两个结点中“数值较小”的那个。

回源：PDF 第 16 页；回源 · PDF 第 16 页 · b_16_4；PDF 第 16 页 · b_16_3；PDF 第 16 页 · b_16_5；PDF 第 16 页 · b_16_7 。正式代码

34｜层序遍历求高度（本章第 7 题）

题目与要求

题目（依据原题整理）：使用层次遍历，求给定二叉树的高度。

已知条件：输入二叉链表的根指针；层次遍历要求先访问上一层，再访问下一层。

需要得到：树共有多少层。本讲解约定空树高度为 0，只有一个根结点时高度为 1。

输入 → 输出示例（教学补充）：A 为根，A 的左孩子 B，B 的左孩子 C → 一共 3 层，返回 3。

约定与提醒（教学补充）：不要把根到最深叶子的边数 2 当作本例高度。题目指定用层次遍历，本节因此练习队列与分层计数；定长队列需足够容纳代码运行中的入队结点。

题干回源：Code59 PDF 第 17 页；回源 · PDF 第 17 页 · b_17_0；PDF 第 17 页 · b_17_1 。

1. 高度是在问树有多少层

根算第 1 层。A 的孩子 B、C，B 再有孩子 D，则高度是 3。空树高度为 0。BFS 像按楼层点名，每完成一层把 height 加一。

front 是下一待取位置，rear 是下一可写位置。levelEnd 是本层开始时把 rear 拍下的快照，后面 rear 增加，也不能让 levelEnd 跟着变。

2. 让新来的下一层先排着，不提前处理

本层开始	front、rear、levelEnd	本层出队谁	新入队谁	本层结束高度
队列 A	0、1、1	A	B、C，rear 到 3	1
待处理 B、C	1、3、3	B、C	D，rear 到 4	2
待处理 D	3、4、4	D	无	3

第一层处理 A 时，rear 已增长到 3，但 front 到旧边界 1 就应结束本层，否则会把 B、C 算作同一层。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

int treeHeightByLevelOrder(BiTree root) {
    if (root == NULL)
        return 0;

    BiTree queue[MAXSIZE];
    int front = 0, rear = 0;
    int height = 0;
    queue[rear++] = root;

    while (front < rear) {
        int levelEnd = rear;
        while (front < levelEnd) {
            BiTree node = queue[front++];
            if (node->lchild != NULL)
                queue[rear++] = node->lchild;
            if (node->rchild != NULL)
                queue[rear++] = node->rchild;
        }
        height++;
    }

    return height;
}

空树先 return 0。queue 数组存结点地址；front、rear、height 清零。queue[rear++]=root 先在第 0 格放 root，再 rear 变 1。

外 while 检查是否还有待处理结点。每轮固定 levelEnd；内 while 只取到旧边界。node=queue[front++] 取一个结点并前进 front，有左孩子就入队、有右孩子也入队，两个 if 独立。内循环结束后才 height++，表示整层完成。外循环再检查下一层是否存在，最后返回总层数。

4. 自己试一下

单根树：初始队列只有根，处理一次，没有孩子，height=1、front=rear，结束。若把 height++ 放到每次出队处，就变成数结点数而非层数。数组队列的下标一直增长，本代码容量必须够容纳所有入队结点。

学懂后回看：结论、复杂度与回源

题意与结论：BFS 一层一层处理，每处理完一整层，高度加 1。关键是冻结本层边界，不能把刚入队的下一层也算进来。

思路推导：普通 BFS 只告诉我们访问顺序；高度需要知道“何时换层”。在本层开始时令 levelEnd=rear，本轮只弹出到这个旧队尾为止，后续入队孩子留给下一轮。

走一遍：A 的孩子 B、C，B 的孩子 D。初始队列 [A]，levelEnd=1，处理 A 后队尾扩到 3，但本层结束，高度 1；第二层处理 B、C，D 入队，高度 2；第三层只处理 D，高度 3。

代码抓手与正确性：外循环 front<rear 表示还有层；内循环 front<levelEnd 表示本层没处理完；height 在内循环结束后增加。归纳地看，每轮开始队列中的待处理部分恰好是一层，所以轮数就是高度。

复杂度与易错点：时间 O(n)；正式数组队列工作空间 O(n)。空树返回 0，单根返回 1。正式实现 front/rear 只增不回绕，MAXSIZE 要能容纳全部入队结点，不能只按最大层宽分配后仍套用这段代码。

回源：PDF 第 17 页；回源 · PDF 第 17 页 · b_17_0；PDF 第 17 页 · b_17_1；PDF 第 17 页 · b_17_3 。正式代码

35｜二叉树带权路径长度 WPL（本章第 8 题，2014）

题目与要求

题目（依据原题整理）：计算给定二叉树的带权路径长度 WPL。它等于所有叶子结点的“权值 × 从根到该叶子的路径长度”之和。

已知条件：每个叶子有数值权重；路径长度按经过的边数计算，根的深度为 0。

需要得到：一个总和值，只统计叶子，不将内部结点的权值加入结果。

输入 → 输出示例（教学补充）：根的左叶子权值为 2；右孩子是内部结点，其左右叶子权值为 3、5 → WPL=2×1+3×2+5×2=18。

约定与提醒（教学补充）：只含一个叶子根时 WPL 为 0，不是它的权值。本稿使用独立的数值型 weight 字段，不能把字符 '5' 的编码直接当作权重 5；这是锁定稿的校订。

题干回源：Code59 PDF 第 17 页；回源 · PDF 第 17 页 · b_17_4；PDF 第 17 页 · b_17_5 。

1. 权值乘走过的边数，只算叶子

WPL 可以理解成：每个叶子有一个重量，重量乘它离根的路长，再把这些乘积加起来。根深度为 0，因为从根走到自己不用经过边；下一层深度为 1。

例子：根左边直接接权 2 的叶子，右边是内部结点，右子树的两叶权为 3、5。答案 2×1+3×2+5×2=18。内部结点不单独贡献权值。

2. 把递归的返回数写出来

位置	传入 depth	是否叶子	返回什么
左叶，权 2	1	是	2
右子树左叶，权 3	2	是	6
右子树右叶，权 5	2	是	10
右内部结点	1	否	左右相加 16
根	0	否	2+16=18

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

typedef struct WeightedBTNode {
    int weight;
    struct WeightedBTNode *lchild;
    struct WeightedBTNode *rchild;
} WeightedBTNode, *WeightedBiTree;

代码段 2

↑ 回到本题题目

long long weightedPathLength(WeightedBiTree root, int depth) {
    if (root == NULL)
        return 0;

    if (root->lchild == NULL && root->rchild == NULL)
        return (long long)root->weight * depth;

    return weightedPathLength(root->lchild, depth + 1)
         + weightedPathLength(root->rchild, depth + 1);
}

代码段 3

↑ 回到本题题目

long long weightedPathLengthByLevel(WeightedBiTree root) {
    if (root == NULL)
        return 0;

    WeightedBiTree queue[MAXSIZE];
    int front = 0, rear = 0;
    int depth = 0;
    long long wpl = 0;
    queue[rear++] = root;

    while (front < rear) {
        int levelEnd = rear;
        while (front < levelEnd) {
            WeightedBiTree node = queue[front++];
            if (node->lchild == NULL && node->rchild == NULL)
                wpl += (long long)node->weight * depth;
            if (node->lchild != NULL)
                queue[rear++] = node->lchild;
            if (node->rchild != NULL)
                queue[rear++] = node->rchild;
        }
        depth++;
    }

    return wpl;
}

第一段是权重结点类型。weight 用 int 存数值，别拿字符 '5' 的编码直接乘。第二段递归版：空子树贡献 0；叶子直接返回 weight×depth；非叶把左右递归结果相加，递归深度各加 1。(long long) 先把权值扩成较宽整数再乘，减少 int 乘法先溢出的风险。初次调用必须传 depth=0。

第三段层序版：队列保存加权结点地址，depth=0、wpl=0。每轮固定 levelEnd；取到叶子才给 wpl 加 weight*depth，孩子存在则入队；一整层处理完才 depth++。它和求高度用同样层边界，但不是每个结点都加一，而是在叶子上加不同贡献。

4. 自己试一下

只有一个根、权 8：根也是叶子，路径长 0，所以 WPL=0，不是 8。两个叶权 2、5 都直接接根：WPL=2+5=7。若把第 1 层的层号 1 当作根深度，会让每个叶子的路长多 1；高度题和 WPL 题的这个口径必须分清。

学懂后回看：结论、复杂度与回源

题意与结论：WPL=Σ(叶子权值×根到该叶子的边数)，只累加叶子，根深度从 0 开始。可 DFS 传深度，也可 BFS 按层计深度。

思路推导：一条根到叶路径每经过一条边，深度加一。内部结点只是通道，不是本题需要累加的对象；所以递归到叶子才产生 weight*depth 的贡献。

走一遍：根左边直接是权 2 的叶子；右边是内部结点，其两叶权为 3、5。三叶深度分别 1、2、2，故 WPL=2×1+3×2+5×2=18。若把根算第 1 层并直接当路径长度，会多算各叶权值之和 10。

代码抓手与正确性：DFS 初始 depth=0，空子树贡献 0，叶子返回乘积，内部结点返回两孩子贡献之和。BFS 版本每处理完一层才把 depth 加一，同样仅在叶子处累加。各叶恰访问一次，贡献既不漏也不重。

复杂度与易错点：时间均 O(n)；DFS 栈 O(h)，正式 BFS 队列 O(n)。正式校订版专用数值权重结点 WeightedBTNode，不能把普通字符结点的编码当作数值权重。单独一个根若也是叶子，路径长 0，WPL 为 0。大权值需宽整数累加。

回源：PDF 第 17 页；回源 · PDF 第 17 页 · b_17_4；PDF 第 17 页 · b_17_5；PDF 第 17 页 · b_17_6；PDF 第 17 页 · b_17_8 。正式代码

36｜二叉树宽度（本章第 9 题）

题目与要求

题目（依据原题整理）：给定一棵二叉树，求它的宽度，即结点数最多的一层中实际有多少个结点。

已知条件：输入二叉链表的根指针；从根开始逐层统计实际存在的结点。

需要得到：各层结点数的最大值，而不是层数或整棵树的结点总数。

输入 → 输出示例（教学补充）：某树从上到下每层分别有 1、2、3、1 个结点 → 宽度为 3。

约定与提醒（教学补充）：本题不把同层两个结点之间的空槽计入宽度；这与某些平台“包含空位置跨度”的定义不同。空树宽度按 0 处理。

题干回源：Code59 PDF 第 17—18 页；回源 · PDF 第 18 页 · b_18_0；PDF 第 18 页 · b_18_2；PDF 第 17 页 · b_17_7 。

1. 宽度是某一层“实际站了多少个结点”

如果各层人数为 1、2、3、1，宽度就是 3，不是高度 4，也不是总数 7。本题不把两个结点之间的空槽也算进去。

maxWidth 记目前遇过的最大一层人数，width 记本轮这层人数。队列区间的长度等于 rear-front，和数组总容量无关。

2. 人数必须在这一层开始时数

当前层	待处理结点	width	maxWidth 更新后
第 1 层	A	1	1
第 2 层	B、C	2	2
第 3 层	D、E、F	3	3
第 4 层	G	1	仍为 3

处理 B 时，它的孩子已经排进队尾，但 C 还没出队；若这时才看 rear-front，会把本层剩下的 C 和下一层孩子混在一起，不能代表任何完整一层的人数。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

int maxTreeWidth(BiTree root) {
    if (root == NULL)
        return 0;

    BiTree queue[MAXSIZE];
    int front = 0, rear = 0;
    int maxWidth = 0;
    queue[rear++] = root;

    while (front < rear) {
        int levelEnd = rear;
        int width = levelEnd - front;
        if (width > maxWidth)
            maxWidth = width;

        while (front < levelEnd) {
            BiTree node = queue[front++];
            if (node->lchild != NULL)
                queue[rear++] = node->lchild;
            if (node->rchild != NULL)
                queue[rear++] = node->rchild;
        }
    }

    return maxWidth;
}

空树返回 0，初始化队列与 maxWidth。外循环开始时 levelEnd=rear，width=levelEnd-front 数本层；若超过旧纪录，就改 maxWidth，不超过就保留旧纪录。

接着内循环从 front 取到固定 levelEnd，每次取 node 并按左、右顺序加入存在的孩子。它只负责把下一层准备好，不在里面修改本层 width。直到队列空，return maxWidth。

4. 自己试一下

一条只有单孩子的长链每层都只有 1 个，所以无论多高，宽度都为 1。根有两孩子则至少宽度 2。和上一题一样，本实现不是循环复用队列数组空间，不能只开“最大宽度”大小的数组却照旧让 rear 一直增长。

学懂后回看：结论、复杂度与回源

题意与结论：本题宽度是各层实际结点数的最大值。BFS 每层开始时的 rear-front 就是该层结点数，取最大即可。

思路推导：求高度只数“有多少层”，求宽度则比较“每层有几个”。先记录当前层数量，再处理这一层，不能处理途中把下一层孩子混入当前层数量。

走一遍：某树各层结点为 [A]、[B,C]、[D,E,F]、[G]。本层开始的队列待处理长度依次是 1、2、3、1，最大值为 3，因此宽度为 3。

代码抓手与正确性：先冻结 levelEnd=rear，令 width=levelEnd-front 并更新最大宽度；然后只处理到这个本层边界，并把孩子入队。队列保持层次顺序，本轮新增的孩子恰属于下一层。也可 DFS 按深度累加计数，但需要按层计数数组。

复杂度与易错点：时间 O(n)，正式数组队列空间 O(n)；空树宽度 0。这里不是一些编程平台定义的“把中间空位也算上的位置跨度”。即使某层两结点分居很远，本题仍只算 2，而非左右端点下标差加一。

回源：PDF 第 17—18 页；回源 · PDF 第 18 页 · b_18_0；PDF 第 18 页 · b_18_2；PDF 第 17 页 · b_17_7 。正式代码

37｜判断满二叉树（本章第 10 题）

题目与要求

题目（依据原题整理）：判断给定二叉树是否为满二叉树。按本资料采用的口径，高度为 h 的满二叉树恰有 2^h-1 个结点，也就是每一层都填满。

已知条件：输入二叉链表；高度按层数计算，只有根时为 1。

需要得到：满足满二叉树定义返回真，否则返回假。

输入 → 输出示例（教学补充）：A 有左右叶子 B、C → 高度 2、结点数 3，返回真；若再只给 B 增加两个孩子 → 高度 3、结点数 5，返回假。

约定与提醒（教学补充）：第二个例子虽然每个结点的度为 0 或 2，是正则二叉树，但不是满二叉树。空树在本函数中按 h=0、n=0 满足计数等式处理；考试若单独限定非空树，按题设判断。

题干回源：Code59 PDF 第 18 页；回源 · PDF 第 18 页 · b_18_1；PDF 第 18 页 · b_18_4 。

1. “满”是每层应该有的位置一个不缺

高度 1 时最多 1 个结点；高度 2 时最多 1+2=3 个；高度 3 时最多 1+2+4=7 个。全都达到，才叫本题的满二叉树。

nodeCount 记实际结点数，height 记最深层号。root 第一次按第 1 层处理，与 WPL 的根深度 0 不同。

2. 先数实际有多少，再算应该有多少

树的形态	实际层数 h	实际结点数 n	满树应有 2^h-1	结论
根＋两个叶子	2	3	3	是
根仅有一个孩子	2	2	3	否
三层，每层人数 1、2、2	3	5	7	否
三层，每层人数 1、2、4	3	7	7	是

即便每个内部结点都有两个孩子，最后一层也可能缺一半位置，所以前面的正则判断不能代替本题。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

void countNodesAndHeight(BiTree root, int depth,
                         int *nodeCount, int *height) {
    if (root == NULL)
        return;

    (*nodeCount)++;
    if (depth > *height)
        *height = depth;

    countNodesAndHeight(root->lchild, depth + 1, nodeCount, height);
    countNodesAndHeight(root->rchild, depth + 1, nodeCount, height);
}

bool isFullBinaryTree(BiTree root) {
    int nodeCount = 0;
    int height = 0;
    countNodesAndHeight(root, 1, &nodeCount, &height);

    long long expected = (1LL << height) - 1;
    return nodeCount == expected;
}

辅助函数收到 nodeCount、height 的地址，所有递归调用共同修改同一份总计数与最高纪录。每到一个非空结点，(*nodeCount)++ 给总数加一；当前 depth 若更大，就写进 *height；再去两孩子，深度各加一。

主函数的两个整数先设 0；调用时用 & 传地址，根层号传 1。1LL<<height 在这里表示把宽整数 1 左移 h 位，在可表示范围内就是 2 的 h 次方；减一得到 expected。最后比较 nodeCount 与 expected 是否相等，交回真假。

4. 自己试与工程边界

单根：计数 1、高度 1，期望 1，返回 true。空树按代码高度 0、计数 0、期望 0，也返回 true。别背成“任何高度都能安全位移”，过深会超整数位宽；考试小规模下读懂计数定理，通用实现可用左右同高且都满的递归判法。

学懂后回看：结论、复杂度与回源

题意与结论：按本资料与王道口径，高度 h 的满二叉树每层都满，结点总数为 2^h-1。遍历求 n 与 h，再验证等式。

思路推导：高度为 h 的二叉树最多有 1+2+...+2^(h-1) 个结点。如果总数达到这个上界，就不能有任何一层缺结点；因此这个计数条件足以判断。

走一遍：三层结点数为 1、2、4，n=7、h=3，7=2³-1，是满树。若三层为 1、2、2，n=5、h=3，虽可能每个内部结点都有两个孩子（正则），仍有 5<7，不是满树。

代码抓手与正确性：递归中每遇非空结点增加 count，以根为第 1 层更新最大高度；最后比较 (1LL<<height)-1 与结点数。不要把叶子数放进这个等式。正式函数把空树判为 true，可理解为 h=0、n=0 满足等式的实现约定。

复杂度与易错点：时间 O(n)，栈 O(h)。工程边界：1LL<<height 并非对任意高度都安全，接近类型位宽时可能溢出或产生未定义行为。考试按小规模计数理解；通用程序可改为后序返回“高度、是否满”，要求左右均满且高度相同，避免大移位。本讲解不改原代码。

回源：PDF 第 18 页；回源 · PDF 第 18 页 · b_18_1；PDF 第 18 页 · b_18_4 。正式代码

38｜满二叉树先序与后序互转（本章第 11 题）

题目与要求

题目（依据原题整理）：一棵满二叉树的先序遍历序列保存在数组中，设计一个算法，得到它的后序遍历序列。本题代码还给出反方向练习：已知后序序列，求先序序列。

已知条件：题目已保证树是每层都满的二叉树；先序按“根、左、右”排列，后序按“左、右、根”排列。

需要得到：同一棵树的另一种遍历序列，不能改变左右子树的相对身份。

输入 → 输出示例（教学补充）：先序 A B D E C F G → 后序 D E B F G C A；反向输入该后序，得到原先序。

约定与提醒（教学补充）：本例 A 的左右孩子为 B、C，B 的孩子为 D、E，C 的孩子为 F、G。满二叉树这一条件不可省；任意二叉树只给先序通常不能唯一确定后序。

题干回源：Code59 PDF 第 19 页；回源 · PDF 第 19 页 · b_19_0；PDF 第 19 页 · b_19_2 。

1. 先序和后序，差的是根放前还是放后

先序按“根、左子树、右子树”，后序按“左子树、右子树、根”。本题保证是满二叉树，因此左右子树大小相同，才知道怎样切开两个区间。

输入先序 A B D E C F G，输出后序 D E B F G C A。preL/preR 是输入这一段的两端，postL/postR 是输出中预留给这一段的两端，都含端点。

2. 先画格子归属，不要一开始计算四个加减式

当前树	先序里根的位置	左子树的先序	右子树的先序	对应后序
全树	A 在最前	B D E	C F G	左三格，右三格，最后 A
左子树	B 在最前	D	E	D E B
右子树	C 在最前	F	G	F G C

区间共 7 个元素，去掉根余 6，左右各 3。代码中的 (preR-preL)/2 就是 (区间长度-1)/2，并不是忘了加一。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

void preorderToPostorder(char pre[], int preL, int preR,
                         char post[], int postL, int postR) {
    if (preL > preR)
        return;

    post[postR] = pre[preL];
    if (preL == preR)
        return;

    int subtreeSize = (preR - preL) / 2;
    preorderToPostorder(pre, preL + 1, preL + subtreeSize,
                        post, postL, postL + subtreeSize - 1);
    preorderToPostorder(pre, preL + subtreeSize + 1, preR,
                        post, postL + subtreeSize, postR - 1);
}

void postorderToPreorder(char post[], int postL, int postR,
                         char pre[], int preL, int preR) {
    if (postL > postR)
        return;

    pre[preL] = post[postR];
    if (postL == postR)
        return;

    int subtreeSize = (postR - postL) / 2;
    postorderToPreorder(post, postL, postL + subtreeSize - 1,
                        pre, preL + 1, preL + subtreeSize);
    postorderToPreorder(post, postL + subtreeSize, postR - 1,
                        pre, preL + subtreeSize + 1, preR);
}

第一个函数：左端大于右端表示空区间，直接返回；把输入最前的根复制到输出最后；只剩一个元素时已完成，直接返回。否则算 subtreeSize，再分别递归处理左右区间：输入左段从 preL+1 起，长度 subtreeSize；输出左段从 postL 起；输入右段在左段之后，输出右段到 postR-1 为止，因为 postR 已留给根。

第二个函数反向做：输入后序末尾是根，先放到输出先序开头；左子树仍占输入前半，输出则从根后一个位置开始；右子树接在左段后。它们只是写数组，不需要先建出实际结点。

4. 自己试一下

三结点满树，先序 A B C，后序为 B C A；反向读 B C A 的末尾 A 为根，前两段各 1 格，得到 A B C。一般树只凭先序不知左右子树各多大，不能照样均分；“满树”正是这个算法额外得到的信息。

学懂后回看：结论、复杂度与回源

题意与结论：已知满二叉树，左右子树结点数相等。先序中的根在最前，后序中的根在最后，其余左右子树各占一半，递归搬根即可。

思路推导：普通二叉树只看先序无法知道左子树占多少元素；满树的结构补上了这个信息。若当前区间长度为 L，则左右子树长度都为 (L-1)/2。

走一遍：先序 A B D E C F G。A 是根，后面 6 个均分为左 B D E、右 C F G；左转成 D E B，右转成 F G C；最后放根 A，得到后序 D E B F G C A。反向转换则从后序末尾取 A，再分别转换左右两段。

代码抓手与正确性：长度为 1 时直接复制；长度大于 1 时计算半长，递归的输入区间和输出起点必须分别算清。先转后是“左、右、根”，后转先是“根、左、右”。每一步划分恰对应真实子树，因此递归合成序列正确。

复杂度与易错点：时间 O(n)，除输出外递归栈 O(h)；满树 h 为 O(log n)。关键前提是每层都满，不是仅“结点度为 0 或 2”。不满但正则的树，左右子树规模可能不同，不能一分为二。

回源：PDF 第 19 页；回源 · PDF 第 19 页 · b_19_0；PDF 第 19 页 · b_19_2 。正式代码

39｜由遍历序列建立二叉链表（本章第 12 题）

题目与要求

题目（依据原题整理）：一棵二叉树的先序遍历和中序遍历分别存放在两个数组中，根据它们建立对应的二叉链表。另一种情况是给定后序遍历和中序遍历，同样要求建树。

已知条件：输入两种遍历序列及各自有效区间。下面实现的前提是：结点值互不相同，两序列合法且确实来自同一棵树。

需要得到：新建树的根指针，各结点的左右孩子关系应与输入遍历一致。

输入 → 输出示例（教学补充）：先序 A B D E C，中序 D B E A C → A 为根，左孩子 B、右孩子 C，B 的左右孩子为 D、E。该树后序为 D E B C A，与同一中序配对也应建出相同结构。

约定与提醒（教学补充）：中序不可随意换成另一条先序；重复值或不匹配的序列不满足本实现前提。题目要求建立结点与链接，不只是打印序列。

题干回源：Code59 PDF 第 19 页；回源 · PDF 第 19 页 · b_19_5；PDF 第 19 页 · b_19_4；PDF 第 19 页 · b_19_1 。

1. 两种遍历各提供一半信息

先序告诉你“谁是根”：第一位；中序告诉你“哪些在左、哪些在右”：根左侧与右侧。值互异时才能据此唯一切分。本题不是把两个数组简单拼在一起，而是申请结点并设置孩子地址。

输入先序 A B D E C、中序 D B E A C，输出根 A、左子树 B 带 D/E、右孩子 C 的树。后序 D E B C A 搭配同一中序也能建立它。

2. 第一层下标全部算一次

项目	本例数值	意义
preL、preR	0、4	先序完整区间
inL、inR	0、4	中序完整区间
root->data	pre[0]=A	先序首位定根
split	3	中序 A 所在下标
leftSize	3-0=3	中序根左侧三个元素
左子树区间	先序 1..3，中序 0..2	B D E；D B E
右子树区间	先序 4..4，中序 4..4	C；C

递归左树时再从 B 定根，中序 D B E 的根在中间，得到 D 与 E 两个叶子。到单元素时，两边再递归都是空区间，返回 NULL，成为叶子的两个空孩子。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

BiTree buildFromPreIn(char pre[], int preL, int preR,
                      char in[], int inL, int inR) {
    if (preL > preR || inL > inR)
        return NULL;

    BiTree root = (BiTree)malloc(sizeof(BTNode));
    root->data = pre[preL];

    int split = inL;
    while (split <= inR && in[split] != root->data)
        split++;

    int leftSize = split - inL;
    root->lchild = buildFromPreIn(pre, preL + 1, preL + leftSize,
                                  in, inL, split - 1);
    root->rchild = buildFromPreIn(pre, preL + leftSize + 1, preR,
                                  in, split + 1, inR);
    return root;
}

代码段 2

↑ 回到本题题目

BiTree buildFromPostIn(char post[], int postL, int postR,
                       char in[], int inL, int inR) {
    if (postL > postR || inL > inR)
        return NULL;

    BiTree root = (BiTree)malloc(sizeof(BTNode));
    root->data = post[postR];

    int split = inL;
    while (split <= inR && in[split] != root->data)
        split++;

    int leftSize = split - inL;
    root->lchild = buildFromPostIn(post, postL, postL + leftSize - 1,
                                   in, inL, split - 1);
    root->rchild = buildFromPostIn(post, postL + leftSize, postR - 1,
                                   in, split + 1, inR);
    return root;
}

第一段：任一输入区间为空就返回 NULL；malloc 新建根，赋 data 为先序首值；split 从中序左端向右找同值位置。找到后用 split-inL 算左树长度，然后分别递归取得左右子树的根地址，赋给 root->lchild、root->rchild。return root 把整棵新子树的入口交回上一层。

第二段只改定根与切片规则：根取后序 postR；左树的后序从 postL 起，长度 leftSize；右树从 postL+leftSize 起，到 postR-1 结束，不能把末尾根又放进去。中序切分规则与第一段完全一样。

4. 自己试与“不足以唯一确定”

先序 A B、中序 B A：A 为根、B 在左；若中序 A B，则 B 在右。这说明中序提供了关键方向。只有先序 A B 和后序 B A，不能区分这两种树。存在重复值或序列不一致时，当前模板不能可靠处理；正式代码也未检查每次申请失败，实际运行前要满足合法输入前提。

学懂后回看：结论、复杂度与回源

题意与结论：结点值互异且遍历序列合法时，“先序+中序”或“后序+中序”都能唯一建树。先/后序负责定根，中序负责划分左右子树。

思路推导：先序第一个是根，后序最后一个是根；在中序找到这个根，左边全部属于左子树，右边全部属于右子树。中序中的左段长度 leftSize 决定另一个遍历序列应如何分段。

走一遍：先序 A B D E C，中序 D B E A C。先取 A，在中序中 A 左侧有 3 个元素，所以左子树先序 B D E、中序 D B E；右子树只有 C。左边再取 B，得到左孩子 D、右孩子 E。对应后序为 D E B C A，改用末尾 A 定根也得到同一棵树。

代码抓手与正确性：以先序首下标 preL、中序首下标 inL 为例，左子树先序从 preL+1 开始、长度 leftSize；右子树从 preL+1+leftSize 开始。中序根自身不放入任一子树。递归遇空区间返回 NULL，遇非空区间申请根结点后连接左右结果。

复杂度与易错点：正式实现每次线性查找中序根，最坏时间 O(n²)；工作栈 O(h)，新树输出占 O(n)。预建“值→中序位置”表可把查找加速，但需额外空间和唯一值前提。仅先序+后序对一般二叉树不足以唯一重建；重复值也不能直接按此证明唯一。工程实现需处理序列不一致与申请失败。

回源：PDF 第 19 页；回源 · PDF 第 19 页 · b_19_5；PDF 第 19 页 · b_19_4；PDF 第 19 页 · b_19_1 。正式代码

40｜链式树与顺序数组互转（本章第 13 题）

题目与要求

题目（依据原题整理）：给定一棵用二叉链表表示的二叉树，设计一个算法，将它存放到一维数组中。本题还练习反向转换：根据顺序存储数组建立二叉链表。

已知条件：本讲解约定根在下标 0，结点 i 的左、右孩子分别放在 2i+1、2i+2；空位置用字符 '#' 表示。

需要得到：两种存储表示互相转换，但结点的左右位置关系不变。

输入 → 输出示例（教学补充）：A 为根，左孩子 B、右孩子 C，B 只有右孩子 D → 数组有效范围为 [A,B,C,#,D]；反向读它应还原同一棵树。

约定与提醒（教学补充）：数组不是简单的遍历序列，空位置不能随意压缩。数据字符不能使用保留标记 '#'；数组需足够大，稀疏深树所需容量可能远大于实际结点数。

题干回源：Code59 PDF 第 19 页；回源 · PDF 第 19 页 · b_19_3；PDF 第 19 页 · b_19_6 。

1. 数组位置记的是树的形状，不只是数第几个结点

下标 0 给根；任意 i 的左孩子位置为 2i+1，右孩子为 2i+2。某个位置没结点也要留空，不能挤掉后把别人前移。

输入树 A 只有右孩子 C，C 只有左孩子 D；输出数组前六格为 [A,#,C,#,#,D]。# 是本题约定的空槽符号。

2. 逐条边换成下标

从哪个结点出发	它的下标	走哪条边	孩子应放下标
根 A	0	右	2×0+2=2，放 C
C	2	左	2×2+1=5，放 D
A	0	左	1，但没孩子，保留 #
C	2	右	6，但没孩子

只有三个真实结点，却需要至少六个数组格才能覆盖下标 5。真实数量 n 与容量 capacity 不能混同。

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

void treeToArray(BiTree root, char A[], int index, int capacity) {
    if (root == NULL || index >= capacity)
        return;

    A[index] = root->data;
    treeToArray(root->lchild, A, 2 * index + 1, capacity);
    treeToArray(root->rchild, A, 2 * index + 2, capacity);
}

代码段 2

↑ 回到本题题目

BiTree arrayToTree(char A[], int index, int n) {
    if (index >= n || A[index] == '#')
        return NULL;

    BiTree root = (BiTree)malloc(sizeof(BTNode));
    root->data = A[index];
    root->lchild = arrayToTree(A, 2 * index + 1, n);
    root->rchild = arrayToTree(A, 2 * index + 2, n);
    return root;
}

链转数组前，调用者先把全部槽设为 #。函数遇空结点或越界就返回；否则 A[index]=root->data 保存当前值；左右递归只需要把 index 改成对应孩子公式，capacity 原样传下去。根第一次传 index=0。

数组转链：先判断越界或当前为 #，此时不申请结点，返回 NULL。存在才 malloc、赋 data；递归算左、右孩子地址并存到新结点；return root 交回入口。它构造了新结点，与原数组不是同一存储，但结构一致。

4. 自己试与容量陷阱

根 A 只有左孩子 B，B 只有右孩子 D：下标分别 0、1、4，结果 [A,B,#,#,D]。如果只开三个格，D 放不下；正式链转数组函数会返回并截掉 D，不会自动扩容，所以必须先保证容量。# 若是合法数据就不能又当空标记，一般程序可另设 exists 数组。

学懂后回看：结论、复杂度与回源

题意与结论：根放下标 0，左孩子放 2i+1，右孩子放 2i+2，空槽用 '#'。两种表示之间依相同位置规则递归转换。

思路推导：数组下标表达的是完整二叉树中的逻辑位置，不是实际结点的紧凑编号。缺孩子时必须留空槽，否则后面的父子对应关系会错位。

走一遍：A 只有右孩子 C，C 只有左孩子 D。应写 A[0]='A'，A[2]='C'，A[5]='D'，其他槽为 '#'。不能压成 [A,C,D]，因为那会把 C 解释成 A 的左孩子。反向从 0 读取，跳过空的 1，在 2 建 C，再在 5 建 D。

代码抓手与正确性：链转数组先把数组初始化为空标记，再递归写入每个有效位置；数组转链时，先检查越界或空标记，再申请结点并递归两孩子。每条左/右边都映射到规定的下标公式，所以结构被保留。

复杂度与易错点：访问有效树结点为 O(n)，若初始化长度为 N 的数组，还要 O(N)；递归栈 O(h)。N 可能远大于 n，偏斜树的最大下标随高度快速增长。正式链转数组函数遇容量不足直接返回，可能静默截断，因此使用前必须保证容量覆盖最大位置。'#' 不能同时充当合法数据；一般实现可另设存在标记。

回源：PDF 第 19 页；回源 · PDF 第 19 页 · b_19_3；PDF 第 19 页 · b_19_6 。正式代码

41｜统计顺序存储二叉树的叶子（本章第 14 题）

题目与要求

题目（依据原题整理）：已知一棵二叉树采用顺序存储结构，编写算法，统计这棵树中所有叶子结点的个数。

已知条件：输入数组及其有效存储范围；本讲解根下标为 0，空位标记为 '#'，左右孩子下标为 2i+1、2i+2。

需要得到：真实存在、且没有左右孩子的结点总数。

输入 → 输出示例（教学补充）：数组 [A,B,C,#,D] 表示 A 的孩子为 B、C，B 只有右孩子 D → 叶子为 C、D，返回 2。

约定与提醒（教学补充）：空槽本身不是叶子；“孩子不存在”既可能是下标越界，也可能是对应槽为 '#'。数组必须表示合法的树，不能在空父结点下面单独放一个孩子。

题干回源：Code59 PDF 第 20 页；回源 · PDF 第 20 页 · b_20_0；PDF 第 20 页 · b_20_2 。

1. 叶子必须“自己存在，并且两孩子都不存在”

输入顺序树 [A,B,C,#,D,#,#]。B 有右孩子 D，所以 B 不是叶子；C 没孩子，D 也没孩子，共 2 个叶子。

left、right 是可能的孩子位置；leftEmpty、rightEmpty 是那里实际有没有孩子的真假记录。不存在有两种情况：下标越界，或位置在数组里但存 #。

2. 把每个真实结点判一遍

结点下标、值	左位置情况	右位置情况	是否叶子
0，A	1 为 B	2 为 C	否
1，B	3 为 #	4 为 D	否，不能只看左空
2，C	5 为 #	6 为 #	是
4，D	9 越界	10 越界	是

3. 完整函数与逐句说明

代码段 1

↑ 回到本题题目

int countArrayLeaves(char A[], int index, int n) {
    if (index >= n || A[index] == '#')
        return 0;

    int left = 2 * index + 1;
    int right = 2 * index + 2;
    bool leftEmpty = left >= n || A[left] == '#';
    bool rightEmpty = right >= n || A[right] == '#';

    if (leftEmpty && rightEmpty)
        return 1;

    return countArrayLeaves(A, left, n)
         + countArrayLeaves(A, right, n);
}

第一条 if 检查当前 index，自己为空就返回贡献 0；再计算左右位置。left>=n || A[left]=='#' 利用短路：已经越界时就不再去读 A[left]。右边同理。

两个 empty 都为真才 return 1，表示找到当前这个叶子。否则去两孩子递归，把它们返回的叶子数相加。某个孩子为空时它自己返回 0，不需要在父层重复写两套计数规则。

4. 自己试一下

[A,#,B] 的叶子只有 B，答案 1；A 虽有一个空孩子，也不是叶子。[#] 是空树，答案 0；[A] 则 A 自己存在、孩子都越界，答案 1。数组必须表示合法树，不能在空父槽下面放一个“孤儿结点”又要求递归把它算进来。

学懂后回看：结论、复杂度与回源

题意与结论：一个真实存在的结点，如果两个孩子都不存在，就是叶子。孩子不存在包括“下标越界”和“对应槽为空标记”。

思路推导：不能把数组后半段一律当叶子，因为顺序树可能稀疏；也不能只看一个孩子。先判断当前结点存在，再按左右孩子的位置逐一判断。

走一遍：数组 [A,B,C,#,D,#,#]。A 有 B、C，非叶；B 的左槽空、右槽有 D，仍非叶；C 两孩子都为空，是叶；D 的两个孩子下标都越界，也是叶。因此答案为 2。

代码抓手与正确性：先执行 index>=N || A[index]=='#' 则返回 0；再算 left=2*index+1，right=2*index+2。左右均不存在返回 1，否则返回两个子树叶子数之和。每个叶子只在自己的调用中贡献一次。

复杂度与易错点：对合法树结构，时间与可达有效结点数成正比，栈 O(h)；若按整个存储区长度 N 给上界，可写 O(N)。空树返回 0，只有根返回 1。正式参数 n 表示数组长度，不要与实际结点数混用；空父槽下面不应再放孤立“后代”，否则那是非法树表示。

回源：PDF 第 20 页；回源 · PDF 第 20 页 · b_20_0；PDF 第 20 页 · b_20_2 。正式代码