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*i1、2*i2定位左右孩子直接支撑的——这也是自测题第 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^(h1) - 1。树 A 高度 2、应有 7 个节点却只有 6 个树 B 同样缺了节点 2 的两个孩子最后一层未填满。因此二者都不满足。2.3 判定要点小结自测易错点树类型核心判据本题结论完全二叉树只有最后一层可不满且从左到右连续仅树 A 满足严格二叉树每个非叶子节点恰有 2 个孩子仅树 B 满足完美二叉树所有层完全填满两棵都不是三、概念自测题精讲同一棵树的三种深度遍历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, 13.3 源码印证递归三遍历的访问次序tree_node.h 中arrayToTree把层序数组按下标递归建树后binary_tree_dfs.c 的三个递归函数用完全相同的次序把节点值写入辅助数组preOrder先写root-val再递归左、右子树binary_tree_dfs.cinOrder先递归左子树再写根值最后递归右子树binary_tree_dfs.cpostOrder先递归左、右子树最后写根值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 \ 74.2 三个问题的标准答案问题 1查找数字 7 的路径树 A4 → 6 → 73 个节点树 B1 → 2 → 3 → 4 → 5 → 6 → 77 个节点即全树节点数。问题 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设计递归函数返回以当前节点为根的子树的最大深度空节点返回 0非空节点返回max(depth(left), depth(right)) 1。参考实现伪代码/类 Cint 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 实现同源层序遍历要求先进先出天然适合队列对应 BFS关键技巧每轮迭代开始时队列中恰好包含当前层的全部节点——先记录当前队列长度len再循环取出len个节点并收集其值同时把它们的左右孩子入队队列为空时结束得到按层分组的二维结果。仓库源码佐证单层不分组版的 BFS 见 binary_tree_bfs.c 的levelOrder队列入队根节点 → 循环出队、记录值、把左右孩子入队 → 得到层序序列。分组版只需在外层循环增加按当前队列长度取一批节点的逻辑提示 3 正是这一要点。复杂度每个节点入队出队各一次时间 O(n)最坏情况满二叉树最后一层队列中同时存在约(n1)/2个节点空间 O(n)。七、编程题三二叉搜索树的第 k 小元素中序遍历 计数题目要求BST 含 n 个互不相同的节点值升序排列后从 1 开始编号给定根节点与k1 k n返回第 k 小的值。要求在中序遍历过程中直接得出答案禁止先收集全部节点值。解题思路利用 BST 的核心性质——中序遍历序列严格递增见 binary_search_tree.md 的中序遍历的有序性一节按左子树 → 当前节点 → 右子树的顺序递归/迭代每访问一个节点让计数器加 1当计数器首次等于 k 时当前节点值即为答案立即终止遍历。参考实现伪代码/类 Cint kthSmallest(TreeNode *root, int k) { int count 0; // 使用显式栈进行中序遍历遇到第 k 个节点即返回 // ... 栈式迭代中序遍历 ... // 每弹出一个节点count若 count k 则返回 node-val }也可用递归 全局计数器实现先递归左子树再检查计数最后递归右子树计数命中 k 时记录答案并剪枝。复杂度最坏情况下遍历到第 k 个节点即停止时间复杂度 O(h k)h 为树高空间复杂度 O(h)递归栈或显式栈深度。八、从练习到实战如何在仓库中运行与验证查看实现本章全部示例位于 ru/codes/c/chapter_tree含 binary_tree.c节点插入/删除、binary_tree_bfs.c层序、binary_tree_dfs.c三序遍历、binary_search_tree.cBST 增删查、array_binary_tree.c数组表示与 avl_tree.c平衡树构建运行仓库使用 CMake 管理 C 工程按 codes/c/CMakeLists.txt 配置后编译对应目标即可运行输出会直接打印树形结构与遍历序列可与练习答案逐项比对建树工具层序数组建树依赖 utils/tree_node.h 的arrayToTree三遍历与 BFS 示例均已内置[1..7]测试数据是验证本节自测题第 2 题最快捷的途径语言对照同一练习在仓库的 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 相关章节。三道编程题分别对应递归分治队列 BFSBST 性质 遍历剪枝三大范式是后续所有树形算法堆、并查集、图遍历、平衡树的通用脚手架值得反复手写直到闭卷通过。【免费下载链接】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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/9/10 20:14:35 · 阅读 1.2k Hello 算法二叉树章节习题精讲：概念自测与三类经典编程题实战
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*i1、2*i2定位左右孩子直接支撑的——这也是自测题第 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^(h1) - 1。树 A 高度 2、应有 7 个节点却只有 6 个树 B 同样缺了节点 2 的两个孩子最后一层未填满。因此二者都不满足。2.3 判定要点小结自测易错点树类型核心判据本题结论完全二叉树只有最后一层可不满且从左到右连续仅树 A 满足严格二叉树每个非叶子节点恰有 2 个孩子仅树 B 满足完美二叉树所有层完全填满两棵都不是三、概念自测题精讲同一棵树的三种深度遍历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, 13.3 源码印证递归三遍历的访问次序tree_node.h 中arrayToTree把层序数组按下标递归建树后binary_tree_dfs.c 的三个递归函数用完全相同的次序把节点值写入辅助数组preOrder先写root-val再递归左、右子树binary_tree_dfs.cinOrder先递归左子树再写根值最后递归右子树binary_tree_dfs.cpostOrder先递归左、右子树最后写根值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 \ 74.2 三个问题的标准答案问题 1查找数字 7 的路径树 A4 → 6 → 73 个节点树 B1 → 2 → 3 → 4 → 5 → 6 → 77 个节点即全树节点数。问题 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设计递归函数返回以当前节点为根的子树的最大深度空节点返回 0非空节点返回max(depth(left), depth(right)) 1。参考实现伪代码/类 Cint 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 实现同源层序遍历要求先进先出天然适合队列对应 BFS关键技巧每轮迭代开始时队列中恰好包含当前层的全部节点——先记录当前队列长度len再循环取出len个节点并收集其值同时把它们的左右孩子入队队列为空时结束得到按层分组的二维结果。仓库源码佐证单层不分组版的 BFS 见 binary_tree_bfs.c 的levelOrder队列入队根节点 → 循环出队、记录值、把左右孩子入队 → 得到层序序列。分组版只需在外层循环增加按当前队列长度取一批节点的逻辑提示 3 正是这一要点。复杂度每个节点入队出队各一次时间 O(n)最坏情况满二叉树最后一层队列中同时存在约(n1)/2个节点空间 O(n)。七、编程题三二叉搜索树的第 k 小元素中序遍历 计数题目要求BST 含 n 个互不相同的节点值升序排列后从 1 开始编号给定根节点与k1 k n返回第 k 小的值。要求在中序遍历过程中直接得出答案禁止先收集全部节点值。解题思路利用 BST 的核心性质——中序遍历序列严格递增见 binary_search_tree.md 的中序遍历的有序性一节按左子树 → 当前节点 → 右子树的顺序递归/迭代每访问一个节点让计数器加 1当计数器首次等于 k 时当前节点值即为答案立即终止遍历。参考实现伪代码/类 Cint kthSmallest(TreeNode *root, int k) { int count 0; // 使用显式栈进行中序遍历遇到第 k 个节点即返回 // ... 栈式迭代中序遍历 ... // 每弹出一个节点count若 count k 则返回 node-val }也可用递归 全局计数器实现先递归左子树再检查计数最后递归右子树计数命中 k 时记录答案并剪枝。复杂度最坏情况下遍历到第 k 个节点即停止时间复杂度 O(h k)h 为树高空间复杂度 O(h)递归栈或显式栈深度。八、从练习到实战如何在仓库中运行与验证查看实现本章全部示例位于 ru/codes/c/chapter_tree含 binary_tree.c节点插入/删除、binary_tree_bfs.c层序、binary_tree_dfs.c三序遍历、binary_search_tree.cBST 增删查、array_binary_tree.c数组表示与 avl_tree.c平衡树构建运行仓库使用 CMake 管理 C 工程按 codes/c/CMakeLists.txt 配置后编译对应目标即可运行输出会直接打印树形结构与遍历序列可与练习答案逐项比对建树工具层序数组建树依赖 utils/tree_node.h 的arrayToTree三遍历与 BFS 示例均已内置[1..7]测试数据是验证本节自测题第 2 题最快捷的途径语言对照同一练习在仓库的 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 相关章节。三道编程题分别对应递归分治队列 BFSBST 性质 遍历剪枝三大范式是后续所有树形算法堆、并查集、图遍历、平衡树的通用脚手架值得反复手写直到闭卷通过。【免费下载链接】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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考