二叉树经典例题

第 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的左孩子下标为2i1右孩子下标为2i2只需逐个验证所有非叶子节点是否满足堆性质。选项 A序列100,60,70,50,32,65根节点 100左孩子 60、右孩子 70100 ≥ 两者满足大顶堆节点 60左孩子 50、右孩子 3260 ≥ 两者满足节点 70左孩子 6570 ≥ 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对新堆顶执行向下筛选每到一个节点先比较它的所有子节点选出最小值再将父节点与这个最小值比较若父节点更大则交换重复直到满足小顶堆性质。初始小根堆[8,15,10,21,34,16,12]共 7 个元素下标 0~6替换堆顶删除堆顶 8将最后一个元素 12 移到堆顶得到临时序列[12,15,10,21,34,16]。向下调整并统计比较次数第 1 次比较节点 12 的左孩子 15、右孩子 10比较两个子节点选出更小的 10第 2 次比较父节点 12 与最小子节点 10 比较12 10交换两者序列变为[10,15,12,21,34,16]第 3 次比较被交换下去的 12下标 2只有左孩子 16比较 12 和 1612 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。调整下标 2值 7左孩子是下标 5值 177 17交换后序列[5,11,17,2,3,7]调整下标 1值 11左孩子 2、右孩子 3最大子节点为 311 3无需交换调整下标 0值 5左孩子 11、右孩子 17最大子节点为 175 17交换后序列[17,11,5,2,3,7] 被交换下去的 5下标 2继续向下调整左孩子是 75 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替换堆顶删除堆顶 0将最后一个元素 8 移到堆顶得到临时序列[8,3,2,5,7,4,6]向下调整节点 8下标 0左孩子 3、右孩子 2最小子节点为 28 2交换后序列[2,3,8,5,7,4,6]节点 8下标 2左孩子 4、右孩子 6最小子节点为 48 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。输出描述可能有多组测试数据对于每组数据 输出将输入字符串建立二叉树后中序遍历的序列每个字符后面都有一个空格。 每个输出结果占一行。示例1abc##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; }我们用两棵具体的二叉树 逐步骤递归拆解的方式把代码的执行过程完整走一遍先再明确一次核心规则完全对应代码逻辑空节点高度 0天然平衡对任意非空节点遵循「左 → 右 → 根」的后序顺序先算左子树高度leftHeight如果左子树返回-1说明左子树已经不平衡当前节点直接返回-1剪枝不用再算右边再算右子树高度rightHeight如果右子树返回-1当前节点直接返回-1左右都平衡计算高度差的绝对值高度差 1 → 不平衡返回-1高度差 ≤ 1 → 平衡返回max(左高, 右高) 1当前节点的高度示例一平衡二叉树我们用这棵经典平衡树来走完整流程3 ← 根节点 / \ 9 20 / \ 15 7完整执行步骤调用 getHeight(3)进入根节点 3非空先处理左子树 → 调用 getHeight(9)进入节点 9非空先处理左子树 → 调用 getHeight(9的左孩子)左孩子是空节点 → 直接返回 0leftHeight 0不是 - 1继续处理右子树 → 调用 getHeight(9的右孩子)右孩子是空节点 → 直接返回 0rightHeight 0不是 - 1计算高度差|0 - 0| 0 ≤ 1 → 平衡返回当前高度max(0,0) 1 1✅ 节点 9 处理完成向上返回高度 1回到根节点 3leftHeight 1不是 - 1继续处理右子树 → 调用 getHeight(20)进入节点 20非空先处理左子树 → 调用 getHeight(15)节点 15 左右都是空和节点 9 逻辑完全一样最终返回高度 1leftHeight 1不是 - 1继续处理右子树 → 调用 getHeight(7)节点 7 左右都是空同样返回高度 1rightHeight 1不是 - 1计算高度差|1 - 1| 0 ≤ 1 → 平衡返回当前高度max(1,1) 1 2✅ 节点 20 处理完成向上返回高度 2回到根节点 3rightHeight 2计算高度差|1 - 2| 1 ≤ 1 → 平衡返回当前高度max(1,2) 1 3最终判断getHeight(根) 返回 3不是 -1 → isBalanced 返回 true这是一棵平衡二叉树。示例二不平衡二叉树我们用这棵 “左斜树” 演示不平衡的判定过程1 ← 根节点 / 2 / 3完整执行步骤调用getHeight(1)进入根节点 1非空先处理左子树 → 调用getHeight(2)进入节点 2非空先处理左子树 → 调用getHeight(3)进入节点 3左右孩子都是空 高度差为 0平衡 返回高度max(0,0) 1 1✅ 节点 3 处理完成返回高度 1回到节点 2leftHeight 1不是 - 1 处理右子树 → 调用getHeight(2的右孩子)右孩子是空 → 返回0rightHeight 0计算高度差|1 - 0| 1 ≤ 1→ 平衡 返回当前高度max(1,0) 1 2✅ 节点 2 处理完成返回高度 2回到根节点 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)。和代码的对应关系代码逻辑对应作用if (root NULL) return 0;空节点高度为 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;当前节点高度差超限标记不平衡return max(左,右) 1;当前节点平衡返回自身高度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); // 返回 1002. 在平衡二叉树代码里的作用平衡二叉树的判定规则是左右子树高度差的绝对值 ≤ 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 的左子树中包含 subRootroot 的右子树中包含 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); }迭代法层序遍历如果不想用递归可以用队列实现迭代初始化队列把根的左、右孩子依次入队每次出队两个节点进行对比不对称直接返回 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; }