《Hello 算法》二叉树章节习题精解：概念辨析、遍历推导与实战编程

本章习题以「自测 + 动手」两种形式帮助你检验二叉树章节的学习成果：前半部分用层序数组和插入序列来考察满/完全/完美二叉树的区分、三种深度优先遍历的推导，以及二叉搜索树形状对查找效率的影响；后半部分给出三道可直接在面试与刷题平台上验证的编程题——二叉树最大深度、逐层遍历与二叉搜索树第 k 小元素。本文在完整保留原题与官方解答的基础上，结合《Hello 算法》仓库中 en/docs/chapter_tree 的正文讲解与 codes/ 下多种语言的源码实现，逐题给出推理过程、参考代码与复杂度分析，帮助你从「看懂书」走向「写得对」。

习题范围与对应学习资料

本章习题基于以下正文内容出题，做题前建议先复习对应文档：

习题主题	对应正文文档	可配合阅读的源码
满/完全/完美二叉树	binary_tree.md（含二叉树常用术语、最佳与最差结构）	binary_tree.java、binary_tree.py
前序/中序/后序遍历	binary_tree_traversal.md（层序=BFS、DFS 三种顺序）	binary_tree_dfs.java、binary_tree_bfs.java
二叉搜索树查找效率	binary_search_tree.md（查找、插入、删除、退化）	binary_search_tree.java
层序数组与树的对应	array_representation_of_tree.md	array_binary_tree.java

全章知识点回顾与问答可参考 summary.md。仓库为每种语言提供了同一份章节源码，例如 Python 版位于 codes/python/chapter_tree，C 版位于 codes/c/chapter_tree，可在对应语言环境中直接运行验证。

概念复习与详细解析

本部分共三组判断题/推导题，每组均先给出官方解答，再做概念展开，帮助你把「答案」上升为「判定方法」。

1. 满二叉树、完全二叉树与完美二叉树的判定

题目：以下两个数组按层序遍历顺序表示二叉树，None 表示空位：

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

1. 哪棵树是完全二叉树（complete binary tree）？
2. 哪棵树是满二叉树（full binary tree，即每个非叶节点都有两个孩子）？
3. 两棵树中是否有完美二叉树（perfect binary tree）？请分别说明理由。

官方解答：

1. 树 A 是完全二叉树：只有最底层未排满，且最底层节点从左到右连续占据位置。树 B 不是完全二叉树，因为最底层左侧存在空位，而右侧仍有节点（空位在左、节点在右，破坏了「从左到右连续」的要求）。
2. 树 B 是满二叉树：节点 1 和节点 3 各有两个孩子，其余节点均为叶节点。树 A 不是满二叉树：节点 3 只有一个左孩子 6。
3. 两棵树都不是完美二叉树：因为各自的最底层都没有完全填满。

方法提炼：这三类树是 binary_tree.md 中「二叉树的常见类型」一节的核心概念，请抓住它们之间的判定要点：

• 完美二叉树：所有层都被填满，叶节点度为 0，其余节点度均为 2。高度为 h 时总节点数为 2^(h+1) - 1。
• 完全二叉树：只允许最底层不完全填满，且最底层的节点必须从左到右连续摆放。完美二叉树必然是完全二叉树。
• 满二叉树：除叶节点外，每个节点都有两个孩子（每个非叶节点度均为 2）。满二叉树只限制「每个非叶节点必须有两个孩子」，并不要求左右两侧高度对齐。

可以用层序数组来快速完成判定：完美二叉树等价于数组中没有 None 且 2^(h+1)-1 恰好等于节点数；完全二叉树要求 None（若有）只能出现在数组末尾连续段——一旦在某个位置出现空位，其后所有位置都必须是 None；满二叉树则在层序数组中无法用 None 的连续性判断，必须逐节点检查非叶节点是否都恰好有两个孩子。

细节提醒：在中国社区的习惯叫法中，「满二叉树」常被用来称呼 perfect binary tree（完美二叉树），而本书将 perfect / complete / full 三种类型分别译为「完美/完全/满」，做题与交流时注意以题目给出的英文定义为准，避免歧义。这一命名差异在原书 binary_tree.md 中有专门说明。

2. 同一棵树的前序、中序与后序遍历

题目：把数组 [1, 2, 3, 4, 5, 6, 7] 按层序遍历顺序存入一棵完全二叉树。

1. 画出这棵树。
2. 写出它的前序、中序、后序遍历序列。
3. 在中序遍历序列中，根节点 1 左右两侧的子序列分别对应树的哪些部分？

官方解答：

1. 树的形态为：

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

2. 前序遍历为 1, 2, 4, 5, 3, 6, 7；中序遍历为 4, 2, 5, 1, 6, 3, 7；后序遍历为 4, 5, 2, 6, 7, 3, 1。
3. 根节点 1 左侧的序列 4, 2, 5 正是左子树的中序遍历序列；其右侧的 6, 3, 7 正是右子树的中序遍历序列。

推导过程与概念扩展：根据 binary_tree_traversal.md，层序遍历本质是广度优先搜索（BFS），而前序/中序/后序遍历都属于深度优先搜索（DFS），只是访问根节点的时机不同：

• 前序：根 → 左子树 → 右子树；
• 中序：左子树 → 根 → 右子树；
• 后序：左子树 → 右子树 → 根。

以上面的树为例，手工推导三序遍历的通用做法是「以中序为骨架、前/后序定根」：

• 中序序列最有规律：中序遍历左子树得到 4, 2, 5，访问根 1，再中序遍历右子树得到 6, 3, 7，合起来就是 4, 2, 5, 1, 6, 3, 7。这正是第 3 问的答案——中序遍历天然把一棵树按根节点划分为左右两半，这一性质是后续「由遍历序列重建二叉树」（见 build_binary_tree_problem 章节）的基石。
• 前序序列以根开头：先访问 1，随后先遍历左子树（前序得到 2, 4, 5），再遍历右子树（前序得到 3, 6, 7），拼接为 1, 2, 4, 5, 3, 6, 7。
• 后序序列以根结尾：先遍历左子树（后序 4, 5, 2），再遍历右子树（后序 6, 7, 3），最后访问根 1，得到 4, 5, 2, 6, 7, 3, 1。

仓库中的实现可以帮你验证推导结果：在 binary_tree_dfs.java 中，preOrder、inOrder、postOrder 三个递归函数分别按「根→左→右」「左→根→右」「左→右→根」的访问优先级调用 list.add(root.val)，而 main 中通过 TreeNode.listToTree(Arrays.asList(1, 2, 3, 4, 5, 6, 7)) 恰好构建了与本题相同的完全二叉树并打印三种遍历序列，运行后即可看到与官方答案一致的输出。Python 对应版本见 binary_tree_dfs.py。

三种 DFS 的时间复杂度均为 O(n)（每个节点恰好访问一次）；空间复杂度最坏为 O(n)——当树退化为链表时递归深度达到 n。细节可回看 binary_tree_traversal.md 的复杂度分析小节。

3. 两棵二叉搜索树的查找效率对比

题目：把以下序列从左到右依次插入一棵空的二叉搜索树：

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

1. 对每棵树写出查找数值 7 时经过的节点。
2. 若树的高度按「根节点到最远叶节点的边数」计算，两棵树的高度各是多少？
3. 结合前两问，查找 7 在两棵树中的效率是否相同？请用树的形态和查找路径说明。

官方解答：

1. 由序列 A 建成的树，查找路径为 4 → 6 → 7；由序列 B 建成的树，查找路径为 1 → 2 → 3 → 4 → 5 → 6 → 7。
2. 第一棵树的每一层都是满的，高度为 2；第二棵树只有右孩子链，高度为 6。
3. 不相同。插入顺序改变了二叉搜索树的形态与高度：第一棵树查找 7 只需访问 3 个节点，第二棵树要访问全部 7 个节点。树越高，最坏情况下沿路径需要比较的节点就越多。

方法提炼：二叉搜索树（BST）的定义是「左子树所有节点值 < 根节点值 < 右子树所有节点值」，且左右子树本身也是 BST，见 binary_search_tree.md。因此查找时每一步都根据当前节点值与目标值的比较结果，选择左子树或右子树继续下探：

• cur.val < num → 目标在右子树，执行 cur = cur.right；
• cur.val > num → 目标在左子树，执行 cur = cur.left；
• cur.val == num → 找到，退出循环。

序列 A 恰好把中位数 4 先插入作为根，左右子树各 3 个节点，形成完全平衡的形态：高度为 ⌊log₂7⌋ = 2，查找 7 只走 3 个节点。序列 B 则因为每次插入的都是当前最大值，新节点总是成为最右侧节点，最终退化成一条只有右孩子的「链表」，高度为 6，查找退化为线性比较。这正是 binary_tree.md「二叉树的退化」一节描述的两种极端：完美二叉树是理想形态、链表是最差形态——理想时 BST 查找为 O(log n)，退化后所有操作都恶化到 O(n)。

仓库中 binary_search_tree.java 的 search 方法实现了上述循环逻辑；summary.md 的问答部分还补充说明：若要从一组数据构建尽量平衡的 BST，通常的做法是先对数据排序，再取中间元素作为根，递归构建左右子树。AVL 树（见 avl_tree.md）则是通过旋转操作在插入、删除后主动维持平衡，从根本上避免退化。

编程实战与参考实现

本部分三道题均为经典的二叉树算法题，官方教材将其作为章节作业给出，刷题平台上有同名题可供在线验证（对应常见题号：LeetCode 104、102、230）。下面每道题都给出完整可运行的 Python 参考实现（与仓库 TreeNode 定义一致），并说明其与仓库源码的关系与复杂度。

仓库各语言的 TreeNode 定义保持一致，例如 Python 版为：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

可在 binary_tree.py 与 tree_node.h 等处查看多语言节点定义。

编程题一：二叉树的最大深度

题目：给定一棵二叉树的根节点 root（每个节点包含一个整数值以及左右孩子引用），返回树的最大深度。本题中最大深度指根节点到最远叶节点路径上的节点个数，空树的最大深度为 0，要求使用递归实现。

提示：① 本题按「节点个数」计深度，因此只有根节点的树最大深度为 1；② 让递归函数返回以当前节点为根的子树的最大深度；③ 空节点返回 0，非空节点返回 max(左子树深度, 右子树深度) + 1。

参考实现：

def max_depth(root):
    # 空节点对应深度 0（递归基）
    if root is None:
        return 0
    # 分别求左右子树的最大深度，取较大者再加 1（当前节点本身）
    return max(max_depth(root.left), max_depth(root.right)) + 1

要点剖析：

• 度量单位要看清：原书习惯把「高度/深度」定义为路径上的边数（见 binary_tree.md 术语表，并附有 tip 提醒不同教材可能以节点数计，此时数值整体大 1）。而本题明确按节点个数计数，所以只有根节点时深度为 1——上面的 +1 恰恰统计的是当前节点自身。
• 递归基是灵魂：把「空子树深度为 0」作为终止条件，让递归在越过叶节点后自然归零，从而叶节点深度恰好为 1。
• 分治视角：最大深度 = 1 + max(左子树最大深度, 右子树最大深度)，这与书中「树的递归/分治结构」一脉相承，也是后续 AVL 树维护节点高度（updateHeight()）所依赖的核心公式。

复杂度：每个节点访问一次，时间复杂度 O(n)；最坏情况（树退化为链表）递归栈深为 n，空间复杂度 O(n)。

编程题二：逐层遍历二叉树（自顶向下、同层从左到右）

题目：给定根节点 root，借助队列从顶到底、每层从左到右访问所有节点。返回一个二维数组：第一个子数组存放根所在层的值，第二个子数组存放下一层的值，依此类推；空树返回空数组。

提示：① 层序遍历先入队者先被访问，因此要使用队列；② 每轮开始时，队列中的节点恰好都属于同一层；③ 先记录队列长度，再恰好取出这么多节点并入队它们的孩子。

参考实现：

from collections import deque

def level_order_grouped(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)   # 关键：先快照当前层的节点数
        level_vals = []
        for _ in range(level_size):   # 只取出当前层节点
            node = queue.popleft()
            level_vals.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level_vals)   # 一层一个子数组
    return result

要点剖析：

• 与仓库源码的对照：仓库 binary_tree_bfs.java 中的 levelOrder 给出了「打平」的单层队列版层序遍历——根节点入队，出队时把左右孩子依次入队，最终得到 [1, 2, 3, ..., 7] 这样的线性序列。本题只是在每次出队前先快照队列长度 level_size，然后一次性处理恰好 level_size 个节点，从而把序列按层切开。
• 为什么先记录长度：入队孩子会改变队列长度。若不快照，for 循环会「混层」处理。先记录长度、再出队 level_size 个节点，就能保证每轮严格处理一层。
• BFS 的本质：层序遍历是广度优先搜索，对应队列「先进先出」的规则；在书中 binary_tree_traversal.md 里还给出了复杂度分析：时间 O(n)，最坏空间 O(n)（满二叉树时队列中同时最多约 (n+1)/2 个节点）。

复杂度：每个节点恰好入队、出队一次，时间复杂度 O(n)；最坏空间 O(n)。

编程题三：二叉搜索树中的第 k 小元素

题目：一棵二叉搜索树含 n 个值互不相同的节点。把所有节点值从小到大排列后，位置从 1 开始编号。给定根节点 root 与整数 k（满足 1 <= k <= n），返回第 k 位的值。要求在中序遍历过程中直接找出答案，而不是先收集所有节点值再取下标。

提示：① BST 的中序遍历按从小到大访问节点值；② 中序按「左子树 → 当前节点 → 右子树」的顺序处理，访问当前节点时计数器加一；③ 当计数器第一次等于 k 时，当前节点的值即为答案，之后无需再继续遍历。

参考实现：

def kth_smallest(root, k):
    count = 0   # 已访问的节点数（非局部变量，供闭包更新）

    def dfs(node):
        nonlocal count
        if node is None:
            return None
        # 1) 先递归左子树（先访问更小的值）
        left_res = dfs(node.left)
        if left_res is not None:
            return left_res
        # 2) 再访问当前节点：计数器自增并判断是否命中
        count += 1
        if count == k:
            return node.val
        # 3) 最后递归右子树
        return dfs(node.right)

    return dfs(root)

要点剖析：

• 核心性质：BST 的中序遍历序列是递增的，这是 binary_search_tree.md 强调的重要结论——「中序序列 = 升序序列」使 BST 可以 O(n) 时间输出有序数据而无需额外排序。因此「第 k 小」与「中序第 k 个被访问的节点」是同一件事。
• 为何不收集完整序列：朴素做法是先用中序收集长度为 n 的列表再取 arr[k-1]，时间、空间都是 O(n)。题目要求的「边遍历边找」把空间压到 O(h)（h 为树高），命中 k 后立即返回，避免无谓遍历。
• 实现细节：递归到左子树后必须把命中结果向上逐层返回（否则找到答案后仍会继续遍历右子树）；count 用 nonlocal（Python）或类的成员变量（如 binary_search_tree.java 中把计数器封装在类实例内）跨递归层共享计数。仓库 binary_tree_dfs.py 的中序实现 inOrder 展示了标准的「左→根→右」递归骨架，本题只需在「访问根」这一步做计数判断。

复杂度：最坏需遍历到第 k 个节点为止，时间复杂度 O(h + k)（平衡树约 O(log n + k)，最坏退化链表达 O(n)）；若不收集完整序列，空间复杂度为 O(h)，即递归栈深度。

学习闭环与自查清单

做完三组概念题与三道编程题后，可以对照 summary.md 的「重点回顾」自查是否掌握以下要点：

1. 二叉树是体现「一分为二」分治逻辑的非线性结构，节点含值与左右两个孩子引用；
2. 能区分完美、完全、满、平衡四类二叉树，并知道完美二叉树是理想形态、链表是最差退化形态；
3. 理解二叉树可用层序数组表示（父节点与子节点的下标映射，见 array_representation_of_tree.md）；
4. 能说出层序遍历（BFS、用队列）与前/中/后序遍历（DFS、用递归）的实现骨架与复杂度；
5. 掌握 BST 的定义、O(log n) 的增删查、中序递增性质，以及插入顺序如何导致退化。

如需实际运行验证：概念题中的树可以用 TreeNode.listToTree([...])（Java）或对应语言的数组建树工具直接构造，然后调用仓库 binary_tree_dfs 等示例打印遍历序列对照答案；三道编程题则可参照上文的参考实现，在其上扩展测试用例（如空树、单节点树、左右单链树、k = 1 与 k = n 的边界）来巩固对边界条件的理解。