企业官网建设流程全解析

Hello 算法二叉树章节习题精讲：概念自测与三类经典编程题实战

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

本篇技术指南以《Hello 算法》俄语版（ru）二叉树章节的练习题（ru/docs/chapter_tree/exercises.md）为核心骨架，完整还原"概念自测 + 编程实战"两条训练线：自测部分覆盖完全/严格/完美二叉树判定、前序/中序/后序遍历推导、二叉搜索树形态与查找效率对比；编程部分给出最大深度、层序遍历、BST 第 k 小元素三道经典题的思路、提示与参考实现。文中所有结论均与仓库内的 C 语言示例源码（binary_tree_dfs.c、binary_tree_bfs.c、binary_search_tree.c 等）相互印证，读完你既能独立完成本章全部习题，也能理解题目背后的底层数据结构和算法实现。

一、习题前置知识：本章练习对应的二叉树知识地图

在动手做题前，先明确这套练习对应的理论基础。俄语版二叉树章节共四篇正文，练习是它们的综合检验：

• 二叉树基础：节点结构、父/子/叶子节点、子树、高度/深度/度等术语，以及完美、完全、严格、平衡四种常见二叉树定义；
• 二叉树遍历：层序遍历（BFS，队列实现）与前序、中序、后序遍历（DFS，递归实现）及其复杂度分析；
• 二叉搜索树：BST 的性质（左 < 根 < 右）、查找/插入/删除操作、"中序遍历序列递增"这一关键性质，以及退化为链表时的 O(n) 风险；
• 树的数组表示：层序数组与树结构的互相转换规则。

练习中反复出现的"层序数组 + None 占位"写法，正是由 utils/tree_node.h 中的arrayToTree递归建树函数（下标2*i+1、2*i+2定位左右孩子）直接支撑的——这也是自测题第 1、2 题可以直接"看图说话"的物理基础。

二、概念自测题精讲：三类二叉树判定

2.1 题目与树形还原

将两个层序数组还原为树，None表示空位：

• 树 A：[1, 2, 3, 4, 5, 6]
• 树 B：[1, 2, 3, None, None, 6, 7]

按层序下标规则还原后：

树 A: 树 B: 1 1 / \ / \ 2 3 2 3 / \ / / \ / \ 4 5 6 - - 6 7

注意树 B 中节点 2 的两个孩子位置（下标 3、4）为空，而节点 3 的孩子（下标 5、6）分别为 6 和 7。

2.2 三个判定问题的标准答案

问题 1：哪棵树是"完全二叉树"（complete binary tree）？

• 树 A 是完全二叉树：只有最后一层未填满，且该层节点从左到右连续排列（4、5、6 无空缺）。
• 树 B 不是完全二叉树：最后一层左侧（节点 2 的孩子位置）出现空位，而右侧（节点 3 的孩子）仍有节点 6、7，违背了"从左到右连续填充"的要求。

对照正文定义（binary_tree.md）：完全二叉树仅允许最底层不满，且底层节点必须从左到右连续。完美二叉树是完全二叉树的特例。

问题 2：哪棵树是"严格二叉树"（full/strict binary tree，即每个非叶子节点恰有两个孩子）？

• 树 B 是严格二叉树：非叶子节点只有 1 和 3，二者各有左右两个孩子，其余节点均为叶子。
• 树 A 不是严格二叉树：节点 3 只有左孩子 6，缺少右孩子，度为 1，违反"每个非叶子节点都有两个孩子"的定义。

问题 3：是否存在"完美二叉树"（perfect binary tree）？

• 两棵树都不是完美二叉树：完美二叉树要求所有层完全填满、总节点数为2^(h+1) - 1。树 A 高度 2、应有 7 个节点却只有 6 个；树 B 同样缺了节点 2 的两个孩子，最后一层未填满。因此二者都不满足。

2.3 判定要点小结（自测易错点）

三、概念自测题精讲：同一棵树的三种深度遍历

3.1 题目与建树

将层序数组[1, 2, 3, 4, 5, 6, 7]填入完全二叉树，得到：

1 / \ 2 3 / \ / \ 4 5 6 7

这与仓库示例 binary_tree_dfs.c 的 Driver 代码中int nums[] = {1, 2, 3, 4, 5, 6, 7}构造的树完全一致，可以直接运行验证。

3.2 三种遍历序列的标准答案

• 前序遍历（根 → 左 → 右）：1, 2, 4, 5, 3, 6, 7
• 中序遍历（左 → 根 → 右）：4, 2, 5, 1, 6, 3, 7
• 后序遍历（左 → 右 → 根）：4, 5, 2, 6, 7, 3, 1

3.3 源码印证：递归三遍历的访问次序

tree_node.h 中arrayToTree把层序数组按下标递归建树后，binary_tree_dfs.c 的三个递归函数用完全相同的次序把节点值写入辅助数组：

• preOrder：先写root->val，再递归左、右子树（binary_tree_dfs.c）；
• inOrder：先递归左子树，再写根值，最后递归右子树（binary_tree_dfs.c）；
• postOrder：先递归左、右子树，最后写根值（binary_tree_dfs.c）。

3.4 第三问：中序序列的"分治"含义

以根节点 1 为分界，中序序列4, 2, 5 | 1 | 6, 3, 7：

• 根左侧的4, 2, 5恰好是左子树（2、4、5）的中序遍历；
• 根右侧的6, 3, 7恰好是右子树（3、6、7）的中序遍历。

这一性质是后续"由前序/中序重建二叉树"（见 build_tree.c）和"BST 第 k 小元素"等题目的核心依据。

四、概念自测题精讲：两个二叉搜索树的对比

4.1 题目与建树

按从左到右顺序把两组序列依次插入空 BST：

• 序列 A：[4, 2, 6, 1, 3, 5, 7]
• 序列 B：[1, 2, 3, 4, 5, 6, 7]

依据 BST 插入规则（小于走左、大于走右，binary_search_tree.c 的insert正是此实现），得到：

树 A（较平衡）: 树 B（退化为链表）: 4 1 / \ \ 2 6 2 / \ / \ \ 1 3 5 7 3 \ 4 \ 5 \ 6 \ 7

4.2 三个问题的标准答案

问题 1：查找数字 7 的路径

• 树 A：4 → 6 → 7（3 个节点）；
• 树 B：1 → 2 → 3 → 4 → 5 → 6 → 7（7 个节点，即全树节点数）。

问题 2：两棵树的高度（按"根到最远叶子的边数"计）

• 树 A 每层填满，高度为 2；
• 树 B 全部由右孩子构成，高度为 6。

问题 3：查找效率是否相同？

• 不同。插入顺序直接决定了 BST 的形态与高度。树 A 中查找 7 只需比较 3 个节点，树 B 则需要比较全部 7 个节点。BST 的查找时间复杂度是 O(h)（h 为树高）：树越"高"，最坏情况下路径上需要比较的节点就越多；当树退化为链表时，查找退化为 O(n)，完全丧失二叉搜索的 O(log n) 优势。

4.3 源码与理论印证

• BST 的查找实现可见 binary_search_tree.c 的search循环：cur->val < num走右子树、cur->val > num走左子树，与正文 binary_search_tree.md 的说明逐行对应；
• 退化机理的完整阐述见 binary_search_tree.md 的"二叉树搜索树的效率"一节：理想平衡时各操作 O(log n)，持续插入/删除导致退化为链表后各操作恶化到 O(n)；
• 这也正是后续 AVL 树 通过旋转保持平衡的动机所在。

五、编程题一：二叉树的最大深度（递归）

题目要求：给定根节点root，返回最大深度；本题中深度按"节点数"计（根节点深度为 1），空树深度为 0，且必须使用递归。

解题思路：

1. 本题深度按节点数计算：只有根节点的树深度为 1（注意与"按边数计"的定义相差 1）；
2. 设计递归函数返回"以当前节点为根的子树的最大深度"；
3. 空节点返回 0；非空节点返回max(depth(left), depth(right)) + 1。

参考实现（伪代码/类 C）：

int maxDepth(TreeNode *root) { if (root == NULL) { return 0; // 空子树深度为 0 } int leftDepth = maxDepth(root->left); int rightDepth = maxDepth(root->right); return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1; }

复杂度：每个节点恰好访问一次，时间复杂度 O(n)；最坏情况（退化为链表）递归深度为 n，空间复杂度 O(n)，与 binary_tree_traversal.md 中 DFS 的复杂度分析一致。

验证手段：可用 binary_tree_dfs.c 的建树方式构造[1,2,3,4,5,6,7]的完全二叉树，期望返回 3；构造只有右孩子的链表型树，深度等于节点数。

六、编程题二：二叉树的层序遍历（队列）

题目要求：用队列自顶向下、每层从左到右访问所有节点，返回二维数组（第一层一个子数组，依次类推）；空树返回空数组。

解题思路（与仓库 BFS 实现同源）：

1. 层序遍历要求"先进先出"，天然适合队列，对应 BFS；
2. 关键技巧：每轮迭代开始时，队列中恰好包含当前层的全部节点——先记录当前队列长度len，再循环取出len个节点并收集其值，同时把它们的左右孩子入队；
3. 队列为空时结束，得到按层分组的二维结果。

仓库源码佐证：单层不分组版的 BFS 见 binary_tree_bfs.c 的levelOrder：队列入队根节点 → 循环出队、记录值、把左右孩子入队 → 得到层序序列。分组版只需在外层循环增加"按当前队列长度取一批节点"的逻辑，提示 3 正是这一要点。

复杂度：每个节点入队出队各一次，时间 O(n)；最坏情况（满二叉树最后一层）队列中同时存在约(n+1)/2个节点，空间 O(n)。

七、编程题三：二叉搜索树的第 k 小元素（中序遍历 + 计数）

题目要求：BST 含 n 个互不相同的节点，值升序排列后从 1 开始编号；给定根节点与k（1 <= k <= n），返回第 k 小的值。要求在中序遍历过程中直接得出答案，禁止先收集全部节点值。

解题思路：

1. 利用 BST 的核心性质——中序遍历序列严格递增（见 binary_search_tree.md 的"中序遍历的有序性"一节）；
2. 按"左子树 → 当前节点 → 右子树"的顺序递归/迭代，每访问一个节点让计数器加 1；
3. 当计数器首次等于 k 时，当前节点值即为答案，立即终止遍历。

参考实现（伪代码/类 C）：

int kthSmallest(TreeNode *root, int k) { int count = 0; // 使用显式栈进行中序遍历，遇到第 k 个节点即返回 // ... 栈式迭代中序遍历 ... // 每弹出一个节点：count++；若 count == k 则返回 node->val }

也可用递归 + 全局计数器实现：先递归左子树，再检查计数，最后递归右子树；计数命中 k 时记录答案并剪枝。

复杂度：最坏情况下遍历到第 k 个节点即停止，时间复杂度 O(h + k)（h 为树高），空间复杂度 O(h)（递归栈或显式栈深度）。

八、从练习到实战：如何在仓库中运行与验证

1. 查看实现：本章全部示例位于 ru/codes/c/chapter_tree，含 binary_tree.c（节点插入/删除）、binary_tree_bfs.c（层序）、binary_tree_dfs.c（三序遍历）、binary_search_tree.c（BST 增删查）、array_binary_tree.c（数组表示）与 avl_tree.c（平衡树）；
2. 构建运行：仓库使用 CMake 管理 C 工程，按 codes/c/CMakeLists.txt 配置后编译对应目标即可运行，输出会直接打印树形结构与遍历序列，可与练习答案逐项比对；
3. 建树工具：层序数组建树依赖 utils/tree_node.h 的arrayToTree，三遍历与 BFS 示例均已内置[1..7]测试数据，是验证本节自测题第 2 题最快捷的途径；
4. 语言对照：同一练习在仓库的 Python、Java、C++、Go、Rust 等十余种语言中均有对应实现（参见根目录 codes 下各语言chapter_tree目录），可横向比较不同语言对递归与队列的写法差异。

九、练习后的进阶路径

完成本章练习后，可沿以下线索继续深化：

• 数组表示与完全二叉树：array_representation_of_tree.md 解释了自测题第 1、2 题所依赖的层序数组下标规则，也是堆（heap）章节的直接前置；
• AVL 树：自测题第 3 题暴露了 BST 退化问题，avl_tree.md 给出旋转保持平衡的解法，对应代码 avl_tree.c；
• 分治与重建：中序序列的分治性质（自测题第 2 题第 3 问）在 build_tree.c（由前序 + 中序重建二叉树）中有直接应用；
• 二叉树与回溯：树结构是回溯算法的天然载体，可继续阅读 chapter_backtracking 相关章节。

三道编程题分别对应"递归分治""队列 BFS""BST 性质 + 遍历剪枝"三大范式，是后续所有树形算法（堆、并查集、图遍历、平衡树）的通用脚手架，值得反复手写直到闭卷通过。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo