第 1 题

题目：下列关键字序列为堆的是：（） A. 100,60,70,50,32,65 B. 60,70,65,50,32,100 C. 65,100,70,32,50,60 D. 70,65,100,32,50,60 E. 32,50,100,70,65,60 F. 50,100,70,65,60,32

解析： 堆的本质是满足特定性质的完全二叉树，分为大顶堆（每个父节点值 ≥ 左右子节点值）和小顶堆（每个父节点值 ≤ 左右子节点值）。数组下标从 0 开始时，下标i的左孩子下标为2i+1，右孩子下标为2i+2，只需逐个验证所有非叶子节点是否满足堆性质。

• 选项 A：序列100,60,70,50,32,65

  • 根节点 100：左孩子 60、右孩子 70，100 ≥ 两者，满足大顶堆；
  • 节点 60：左孩子 50、右孩子 32，60 ≥ 两者，满足；
  • 节点 70：左孩子 65，70 ≥ 65，满足。 所有节点均满足大顶堆规则，是合法的堆。

• 选项 B：根节点 60 <左孩子 70，不满足大顶堆；节点 70> 子节点 50，也不满足小顶堆，不是堆。

• 选项 C：根节点 65 <左孩子 100，不满足大顶堆；节点 100> 子节点 32，也不满足小顶堆，不是堆。

• 选项 D：根节点 70 <右孩子 100，不满足大顶堆；节点 70> 左孩子 65，也不满足小顶堆，不是堆。

• 选项 E：节点 100 > 左孩子 60，不满足小顶堆，不是堆。

• 选项 F：根节点 50 <左孩子 100，不满足大顶堆；节点 100> 子节点 65，也不满足小顶堆，不是堆。

答案：A

第 2 题

题目：已知小根堆为 8,15,10,21,34,16,12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是（）。 A. 1 B. 2 C. 3 D. 4

解析： 小顶堆删除堆顶的标准流程：

1. 用堆的最后一个元素替换堆顶元素，堆的元素总数减 1；
2. 对新堆顶执行向下筛选：每到一个节点，先比较它的所有子节点选出最小值，再将父节点与这个最小值比较，若父节点更大则交换，重复直到满足小顶堆性质。

初始小根堆：[8,15,10,21,34,16,12]（共 7 个元素，下标 0~6）

1. 替换堆顶：删除堆顶 8，将最后一个元素 12 移到堆顶，得到临时序列[12,15,10,21,34,16]。
2. 向下调整并统计比较次数：
   • 第 1 次比较：节点 12 的左孩子 15、右孩子 10，比较两个子节点，选出更小的 10；
   • 第 2 次比较：父节点 12 与最小子节点 10 比较，12 > 10，交换两者，序列变为[10,15,12,21,34,16]；
   • 第 3 次比较：被交换下去的 12（下标 2）只有左孩子 16，比较 12 和 16，12 < 16，满足小顶堆，调整结束。

总计 3 次比较。

答案：C

第 3 题

题目：一组记录排序码为 (5 11 7 2 3 17)，则利用堆排序方法建立的初始堆为 A. (11 5 7 2 3 17) B. (11 5 7 2 17 3) C. (17 11 7 2 3 5) D. (17 11 7 5 3 2) E. (17 7 11 3 5 2) F. (17 7 11 3 2 5)

解析： 堆排序默认建立大顶堆，建堆规则：从最后一个非叶子节点开始，从下往上、从右往左逐个调整子树，使每个子树都满足大顶堆。 初始序列[5,11,7,2,3,17]共 6 个元素，最后一个非叶子节点下标为 2（值为 7）。

1. 调整下标 2（值 7）：左孩子是下标 5（值 17），7 < 17，交换后序列：[5,11,17,2,3,7]；
2. 调整下标 1（值 11）：左孩子 2、右孩子 3，最大子节点为 3，11 > 3，无需交换；
3. 调整下标 0（值 5）：左孩子 11、右孩子 17，最大子节点为 17，5 < 17，交换后序列：[17,11,5,2,3,7]； 被交换下去的 5（下标 2）继续向下调整：左孩子是 7，5 < 7，交换后序列：[17,11,7,2,3,5]。

最终初始大顶堆为(17 11 7 2 3 5)。

答案：C

第 4 题

题目：最小堆 [0,3,2,5,7,4,6,8]，在删除堆顶元素 0 之后，其结果是（） A. [3, 2, 5, 7, 4, 6, 8] B. [2, 3, 5, 7, 4, 6, 8] C. [2, 3, 4, 5, 7, 8, 6] D. [2, 3, 4, 5, 6, 7, 8]

解析： 小顶堆删除堆顶的操作：末尾元素替换堆顶 → 向下调整至满足小顶堆性质。

初始最小堆：[0,3,2,5,7,4,6,8]（共 8 个元素，下标 0~7）

1. 替换堆顶：删除堆顶 0，将最后一个元素 8 移到堆顶，得到临时序列[8,3,2,5,7,4,6]；
2. 向下调整：
   • 节点 8（下标 0）：左孩子 3、右孩子 2，最小子节点为 2；8 > 2，交换后序列：[2,3,8,5,7,4,6]；
   • 节点 8（下标 2）：左孩子 4、右孩子 6，最小子节点为 4；8 > 4，交换后序列：[2,3,4,5,7,8,6]；
   • 节点 8（下标 5）无有效子节点，调整结束。

最终结果为[2, 3, 4, 5, 7, 8, 6]。

答案：C

第 5 题

描述

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入描述：

输入包括1行字符串，长度不超过100。

输出描述：

可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。

示例1

abc##de#g##f### c b e g d f a

#include <stdio.h> #include <stdlib.h> // 二叉树结点结构体：数据域 + 左右孩子指针 typedef struct BiTNode { char data; struct BiTNode* lchild, *rchild; } BiTNode, *BiTree; // 全局下标：记录当前读取到字符串的第几个字符 int indx; // 递归：按照先序序列创建二叉树，'#' 表示空树 void CreateBiTree(BiTree* T, char str[]) { char ch = str[indx++]; if (ch == '#') { *T = NULL; // 空结点，不分配内存 } else { *T = (BiTree)malloc(sizeof(BiTNode)); (*T)->data = ch; CreateBiTree(&((*T)->lchild), str); // 递归建左子树 CreateBiTree(&((*T)->rchild), str); // 递归建右子树 } } // 中序遍历：左 → 根 → 右，每个字符后带一个空格 void InOrder(BiTree T) { if (T != NULL) { InOrder(T->lchild); printf("%c ", T->data); InOrder(T->rchild); } } int main() { char s[100]; // 多组测试数据：和你图里的 while(scanf...) 框架逻辑完全一致 while (scanf("%s", s) != EOF) { indx = 0; // 【关键】每组用例必须重置下标，从字符串开头重新读 BiTree root; CreateBiTree(&root, s); // 建二叉树 InOrder(root); // 中序遍历输出 printf("\n"); // 每组结果占一行 } return 0; }

第 6 题

给定一个二叉树，判断它是否是 平衡二叉树

// 辅助函数：返回树的高度；若子树不平衡，返回 -1 作为标记 int getHeight(struct TreeNode* root) { // 空树高度为 0 if (root == NULL) { return 0; } // 后序遍历：先处理左子树、再右子树、最后判断当前节点 int leftHeight = getHeight(root->left); // 左子树已经不平衡，直接向上传递标记，无需继续计算 if (leftHeight == -1) { return -1; } int rightHeight = getHeight(root->right); // 右子树已经不平衡，直接向上传递标记 if (rightHeight == -1) { return -1; } // 判断当前节点是否满足平衡条件 if (abs(leftHeight - rightHeight) > 1) { return -1; // 不平衡，返回标记 } // 平衡，返回当前树的高度 = 左右子树最大高度 + 1 return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1; } bool isBalanced(struct TreeNode* root) { // 只要返回值不是 -1，就说明整棵树是平衡的 return getHeight(root) != -1; }

我们用两棵具体的二叉树 + 逐步骤递归拆解的方式，把代码的执行过程完整走一遍

先再明确一次核心规则（完全对应代码逻辑）：

1. 空节点：高度 = 0，天然平衡
2. 对任意非空节点，遵循「左 → 右 → 根」的后序顺序：
   • 先算左子树高度leftHeight
   • 如果左子树返回-1，说明左子树已经不平衡，当前节点直接返回-1（剪枝，不用再算右边）
   • 再算右子树高度rightHeight
   • 如果右子树返回-1，当前节点直接返回-1
   • 左右都平衡：计算高度差的绝对值
     • 高度差 > 1 → 不平衡，返回-1
     • 高度差 ≤ 1 → 平衡，返回max(左高, 右高) + 1（当前节点的高度）

示例一：平衡二叉树

我们用这棵经典平衡树来走完整流程：

3 ← 根节点 / \ 9 20 / \ 15 7

完整执行步骤：调用 getHeight(3)
进入根节点 3
非空，先处理左子树 → 调用 getHeight(9)
进入节点 9
非空，先处理左子树 → 调用 getHeight(9的左孩子)
左孩子是空节点 → 直接返回 0
leftHeight = 0，不是 - 1，继续
处理右子树 → 调用 getHeight(9的右孩子)
右孩子是空节点 → 直接返回 0
rightHeight = 0，不是 - 1
计算高度差：|0 - 0| = 0 ≤ 1 → 平衡
返回当前高度：max(0,0) + 1 = 1
✅ 节点 9 处理完成，向上返回高度 1
回到根节点 3
leftHeight = 1，不是 - 1，继续处理右子树 → 调用 getHeight(20)
进入节点 20
非空，先处理左子树 → 调用 getHeight(15)
节点 15 左右都是空，和节点 9 逻辑完全一样
最终返回高度 1
leftHeight = 1，不是 - 1，继续
处理右子树 → 调用 getHeight(7)
节点 7 左右都是空，同样返回高度 1
rightHeight = 1，不是 - 1
计算高度差：|1 - 1| = 0 ≤ 1 → 平衡
返回当前高度：max(1,1) + 1 = 2
✅ 节点 20 处理完成，向上返回高度 2
回到根节点 3
rightHeight = 2
计算高度差：|1 - 2| = 1 ≤ 1 → 平衡
返回当前高度：max(1,2) + 1 = 3
最终判断
getHeight(根) 返回 3，不是 -1 → isBalanced 返回 true，这是一棵平衡二叉树。

示例二：不平衡二叉树

我们用这棵 “左斜树” 演示不平衡的判定过程：

1 ← 根节点 / 2 / 3

完整执行步骤：调用getHeight(1)

1. 进入根节点 1非空，先处理左子树 → 调用getHeight(2)

2. 进入节点 2非空，先处理左子树 → 调用getHeight(3)

3. 进入节点 3左右孩子都是空 高度差为 0，平衡 返回高度：max(0,0) + 1 = 1

   ✅ 节点 3 处理完成，返回高度 1

4. 回到节点 2leftHeight = 1，不是 - 1 处理右子树 → 调用getHeight(2的右孩子)

   • 右孩子是空 → 返回0rightHeight = 0计算高度差：|1 - 0| = 1 ≤ 1→ 平衡 返回当前高度：max(1,0) + 1 = 2

   ✅ 节点 2 处理完成，返回高度 2

5. 回到根节点 1leftHeight = 2，不是 - 1 处理右子树 → 调用getHeight(1的右孩子)

   • 右孩子是空 → 返回0rightHeight = 0计算高度差：|2 - 0| = 2 > 1→ ❌ 不平衡！ 直接返回标记-1

最终判断

getHeight(根)返回-1→isBalanced返回false，这不是平衡二叉树。

示例三：子树先不平衡，提前剪枝

这是最能体现 “自底向上” 优势的场景：子树已经不平衡了，上层就不用再计算了。

1 / \ 2 3 / 4 / 5

关键流程
递归到最底层节点 5 → 返回高度 1
节点 4：左高 1，右高 0 → 差 1，平衡，返回高度 2
节点 2：左高 2，右高 0 → 差 2 > 1 → 不平衡，返回 -1
回到根节点 1：拿到左子树返回值 -1
→ 触发代码里 if (leftHeight == -1) return -1;
→ 直接返回 -1，完全不用再去计算右子树 3 的高度
这就是 “剪枝”：只要发现某一棵子树不平衡，就立刻把 -1 一路传上去，整条路径都不用再做多余计算，时间复杂度降到 O (n)。

和代码的对应关系

abs函数

abs 是 C 语言标准库中的函数，全称 absolute value，作用是计算一个整数的绝对值。

1. 基本用法

头文件：#include <stdlib.h>
函数原型：int abs(int x);
功能：传入一个整数 x，返回它的绝对值（非负值）。
举几个简单例子：

abs(5); // 返回 5 abs(-3); // 返回 3 abs(0); // 返回 0 abs(-100); // 返回 100

2. 在平衡二叉树代码里的作用

平衡二叉树的判定规则是：左右子树高度差的绝对值 ≤ 1。
我们不关心 “左子树更高” 还是 “右子树更高”，只关心两者相差多少。
如果不用 abs，你需要写成：

if (leftHeight - rightHeight > 1 || rightHeight - leftHeight > 1) { // 不平衡 }

用 abs 之后可以简化成一行：

if (abs(leftHeight - rightHeight) > 1) { // 不平衡 }

无论结果是正还是负，取绝对值后都能统一判断差值是否超过 1，代码更简洁直观。

3. 补充说明

abs 只处理 int 类型的整数。
如果要计算浮点数的绝对值，需要用 fabs 函数，头文件是 <math.h>。
对于 long、long long 类型，对应有 labs、llabs 函数，用法完全一致。

第 7 题

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

核心思路

要判断 subRoot 是不是 root 的子树，本质是两件事：
遍历大树：逐个检查 root 中的每一个节点，把它当作 “可能的根起点”
相同树校验：对每个候选起点，判断以它为根的子树，是否和 subRoot 在结构、节点值上完全一致
只要 root 中存在任意一个节点，满足「以该节点为根的树 ≡ subRoot」，就返回 true。

步骤 1：实现辅助函数 —— 判断两棵树是否完全相同

这是递归的基础：输入两棵树的根节点，返回它们是否完全相等。
递归逻辑
终止条件
两个节点同时为空 → 结构一致，返回 true
一个为空、一个不为空 → 结构不一致，返回 false
两个节点的值不相等 → 值不匹配，返回 false
递归递推
当前节点值相等时，同时递归校验左子树、右子树是否都相同（必须同时满足）

步骤 2：主逻辑 —— 遍历大树，逐个校验

对 root 做深度优先遍历，每到一个节点就启动一次「相同树校验」。
递归逻辑
终止条件：root 为空时，不可能包含非空子树，直接返回 false
递归递推：三种情况满足任意一个即返回 true
以当前 root 节点为根的树，和 subRoot 完全相同
root 的左子树中，包含 subRoot
root 的右子树中，包含 subRoot

#include <stdbool.h> // 二叉树节点定义（LeetCode 题目已内置，本地编译需保留） struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; // 辅助函数：判断两棵树是否完全相同 bool isSameTree(struct TreeNode* p, struct TreeNode* q) { // 两节点同时为空，结构一致 if (p == NULL && q == NULL) { return true; } // 一个为空、一个非空，结构不一致 if (p == NULL || q == NULL) { return false; } // 当前节点值不相等，直接不匹配 if (p->val != q->val) { return false; } // 递归校验左右子树必须同时相等 return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); } // 主函数：判断 subRoot 是否是 root 的子树 bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) { // 大树遍历到空节点，不可能包含子树 if (root == NULL) { return false; } // 三种情况满足其一即可： // 1. 当前节点为根的树 和 subRoot 完全相同 // 2. subRoot 存在于 root 的左子树中 // 3. subRoot 存在于 root 的右子树中 return isSameTree(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot); }

代码说明
isSameTree 辅助函数
用递归逐节点对比：先判空、再判值、最后递归左右子树，保证结构和值完全一致。
时间复杂度：O(n)，n 为两棵树中较小的节点数。
isSubtree 主逻辑
对 root 做深度优先遍历，每遇到一个节点就启动一次 isSameTree 校验。
利用逻辑或||的短路特性：只要找到一个匹配的子树，就会提前返回，不再继续递归。
复杂度
时间复杂度：最坏 O(m * n)（m 是 root 节点数，n 是 subRoot 节点数）。
空间复杂度：O(m)，由递归栈深度决定。

第 8 题

给你一个二叉树的根节点root， 检查它是否轴对称。

递归法

核心思路

镜像对称的两个子树，需要同时满足三个条件：
两个根节点的值相等
左子树的左孩子 与 右子树的右孩子 镜像对称（外侧对应）
左子树的右孩子 与 右子树的左孩子 镜像对称（内侧对应）
我们通过一个辅助递归函数专门判断「两棵树是否互为镜像」，主函数只需要传入根节点的左右孩子即可。

#include <stdbool.h> // 二叉树节点定义（LeetCode 题目已内置，本地编译需保留） struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; // 辅助函数：判断两棵树是否互为镜像 bool isMirror(struct TreeNode* p, struct TreeNode* q) { // 两节点同时为空 → 镜像对称 if (p == NULL && q == NULL) { return true; } // 一个为空、一个非空 → 结构不对称 if (p == NULL || q == NULL) { return false; } // 值不相等 → 不匹配 if (p->val != q->val) { return false; } // 递归核心：外侧对比 + 内侧对比，必须同时满足 return isMirror(p->left, q->right) && isMirror(p->right, q->left); } // 主函数：判断整棵树是否轴对称 bool isSymmetric(struct TreeNode* root) { // 空树默认是对称的 if (root == NULL) { return true; } // 校验左右子树是否镜像 return isMirror(root->left, root->right); }

迭代法（层序遍历）

如果不想用递归，可以用队列实现迭代：

1. 初始化队列，把根的左、右孩子依次入队
2. 每次出队两个节点进行对比
3. 不对称直接返回 false；对称则按「左左、右右、左右、右左」的顺序入队，保证每次出队的都是需要对比的镜像节点

迭代法本质是把递归的「两两镜像对比」逻辑，用队列手动维护待对比的节点对，避免递归栈调用。核心规则：
初始将根节点的左、右孩子作为第一对入队
每次从队列中取出两个节点进行镜像对比
若匹配成功，则按「镜像配对规则」继续入队下一级节点：
左树的左孩子 ↔ 右树的右孩子（外侧配对）
左树的右孩子 ↔ 右树的左孩子（内侧配对）
全程只要出现一对不匹配，直接返回 false；队列为空仍未失败，则返回 true
注意：空节点也必须入队，否则无法识别「结构不对称」的情况。

C 语言没有标准队列库，这里用数组模拟队列

#include <stdbool.h> #include <stdlib.h> // 二叉树节点定义（LeetCode 已内置，本地编译需保留） struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; bool isSymmetric(struct TreeNode* root) { // 空树默认对称 if (root == NULL) { return true; } // 数组模拟队列，存储节点指针 // 题目节点数上限 1000，开 2000 容量足够 struct TreeNode** queue = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 2000); int front = 0; // 队头（出队位置） int rear = 0; // 队尾（入队位置） // 初始入队第一对：左孩子、右孩子 queue[rear++] = root->left; queue[rear++] = root->right; while (front < rear) { // 每次出队两个节点进行对比 struct TreeNode* p = queue[front++]; struct TreeNode* q = queue[front++]; // 两节点都为空：结构对称，跳过 if (p == NULL && q == NULL) { continue; } // 一个空、一个非空：结构不对称 if (p == NULL || q == NULL) { free(queue); return false; } // 值不相等：不匹配 if (p->val != q->val) { free(queue); return false; } // 按镜像规则入队下一级：外侧一对 + 内侧一对 queue[rear++] = p->left; queue[rear++] = q->right; queue[rear++] = p->right; queue[rear++] = q->left; } free(queue); return true; }

第 9 题

给你一棵二叉树的根节点root，翻转这棵二叉树，并返回其根节点。

递归实现（最简洁）

核心思路
终止条件：节点为空时，直接返回 NULL
当前层操作：交换当前节点的 left 和 right 指针
递归深入：分别翻转左子树、右子树
返回值：返回翻转后的当前节点

#include <stdlib.h> // 二叉树节点定义（LeetCode 已内置，本地编译需保留） struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; struct TreeNode* invertTree(struct TreeNode* root) { // 空节点直接返回 if (root == NULL) { return NULL; } // 交换当前节点的左右孩子指针 struct TreeNode* temp = root->left; root->left = root->right; root->right = temp; // 递归翻转左右子树 invertTree(root->left); invertTree(root->right); return root; }