Hello Algo 分治算法练习精解：从适配性判断到快速幂的递归实现

2026-09-06 13:43:19作者：冯爽妲Honey

本篇基于《Hello 算法》仓库的分治算法练习展开，覆盖"判断任务是否适合分治"、"快速幂递归过程手工推演"、"从遍历序列拆分左右子树"三道知识巩固题，以及"快速幂"编程题的完整解法。读完后你能掌握分治三判断依据的应用方法、能独立推演递归分治的调用与回溯过程，并写出带边界处理与溢出防护的可运行快速幂代码。

一、哪些任务适合分治

题目

一位同学想用"先分成两半，分别解决，再合并结果"的方法完成以下任务，请分别判断它们是"适合分治"、"可以分治，但不会减少总工作量"还是"两半不能独立解决"，并说明理由：

将一个无序数组排序；
求一个数组中的最大值；
按顺序执行一串 push(x)、pop() 栈操作，并输出每次 pop() 得到的元素。

判断依据

分治算法的"分（划分阶段）"是递归地将原问题分解为两个或多个子问题直至最小子问题，"治（合并阶段）"是从底至顶地将子问题的解合并为原问题的解（详见分治算法章节）。一个问题是否适合分治，参考以下三个判断依据：

问题可以分解：原问题可以分解成规模更小、类似的子问题，并能以相同方式递归地划分；
子问题是独立的：子问题之间没有重叠，互不依赖，可以独立解决；
子问题的解可以合并：原问题的解通过合并子问题的解得来。

参考答案

适合：对半分解、两半独立排序、 $O (n)$ 合并——这正是归并排序。它完整满足三条依据：数组可以递归对半划分；两个子数组可以独立排序；两个有序子数组可以线性合并为有序数组。
可以分治，但不会减少总工作量：左右两半仍需合计检查全部 $n$ 个元素，和直接扫描一样都是 $O (n)$ 时间。分治在这里"能做但不划算"——子问题虽独立，合并阶段（比较两个最大值）并未换来复杂度上的收益。
两半不能独立解决：后半段开始时的栈内容取决于前半段执行结果，两半不能在互不知道结果时独立完成。这违反了"子问题是独立的"这一核心条件，因此整个操作序列无法被切分处理。

二、快速幂是怎样减少计算的

题目与源码

下面的递归函数用分治计算 $x^{n}$ （多语言实现见 Python 版、Java 版、C++ 版、Rust 版、TypeScript 版，逻辑完全一致）：

def fast_pow(x: int, n: int) -> int:
    """快速幂"""
    if n == 0:
        return 1
    half = fast_pow(x, n // 2)
    if n % 2 == 0:
        return half * half
    return half * half * x

代码结构印证了分治的两个阶段：fast_pow(x, n // 2) 是"分"——把指数缩小一半递归求解；half * half（必要时再乘 x）是"治"——把子问题的解合并为当前层的结果。

令 x = 3、n = 5，请回答：

递归调用时，参数 n 依次变成哪些值？
从最深层开始返回时，各层依次返回什么值？
为什么要先把递归结果保存为 half，而不是在乘法两边各调用一次相同的子问题？

参考答案与逐层推演

第 1 问：参数依次为 5 → 2 → 1 → 0，每次都把指数减半（整除），直到到达终止条件 n == 0。

第 2 问：从最深层自底向上回溯：

返回层	计算过程	返回值
`n = 0`	终止条件直接返回	1
`n = 1`（奇数）	$1 \times 1 \times 3$	3
`n = 2`（偶数）	$3 \times 3$	9
`n = 5`（奇数）	$9 \times 9 \times 3$	243

最终 fast_pow(3, 5) = 243。仓库源码中的自测断言也验证了这一结果（assert fast_pow(3, 5) == 243，见 fast_power.py）。

第 3 问：如果在乘法两边各调用一次相同的子问题，两次递归会进行完全相同的计算。先把结果保存为 half，每层就只递归一次，递归深度约为 $\log n$ ，从而把朴素连乘 $O (n)$ 次的操作量降为 $O(\log n)$ 次乘方结构；而调用两次则会造成大量重复计算，递归树规模按 $2^{\log n} = n$ 增长，分治的效率优势荡然无存。这正是分治与"暴力递归"的关键差别：子问题必须不重叠或被显式复用。

三、从遍历序列拆分左右子树

题目

一棵没有重复节点的二叉树，其前序遍历和中序遍历分别为：

前序遍历：[A, B, D, E, C]
中序遍历：[D, B, E, A, C]

只完成根节点这一层的拆分，不必继续递归，也不必画出整棵树。请回答：

根节点是什么？
左、右子树在中序遍历中分别对应哪一段？
左、右子树在前序遍历中分别对应哪一段？根节点有哪些直接孩子？

参考答案

前序遍历的第一个节点是根节点，因此根节点为 A。
A 把中序遍历分成两部分：左子树为 [D, B, E]，右子树为 [C]。
左子树有 3 个节点，因此根节点 A 后面的 3 个前序元素属于左子树，即 [B, D, E]；剩余的 [C] 属于右子树。所以根节点的左孩子是 B，右孩子是 C。

源码印证：分治如何落到索引区间上

这道题的完整解法在构建二叉树问题中展开，其核心是三个指针变量：当前树根节点在 preorder 中的索引 $i$ 、根节点在 inorder 中的索引 $m$ 、当前树在 inorder 中的索引区间 $[l, r]$ 。子问题的区间由此精确给出：

	根节点在 `preorder` 中的索引	子树在 `inorder` 中的索引区间
当前树	$i$	$[l, r]$
左子树	$i + 1$	$[l, m - 1]$
右子树	$i + 1 + (m - l)$	$[m + 1, r]$

仓库中 build_tree.py 的实现与上表一一对应：

def dfs(preorder, inorder_map, i, l, r) -> TreeNode | None:
    """构建二叉树：分治"""
    if r - l < 0:                      # 子树区间为空时终止
        return None
    root = TreeNode(preorder[i])       # 初始化根节点
    m = inorder_map[preorder[i]]       # 查询 m ，从而划分左右子树
    root.left = dfs(preorder, inorder_map, i + 1, l, m - 1)       # 子问题：左子树
    root.right = dfs(preorder, inorder_map, i + 1 + m - l, m + 1, r)  # 子问题：右子树
    return root

其中 inorder_map 是元素到索引的哈希表，把每次查找 $m$ 的 $O (n)$ 降为 $O (1)$ ，使整体构建过程为 $O (n)$ 时间。注意右子树根节点索引 $i + 1 + (m - l)$ 中 $(m - l)$ 的含义是"左子树的节点数量"——这与上面第 3 问"左子树有 3 个节点，故取 A 后面 3 个前序元素"的推理是同一个数学事实。

四、编程练习：快速幂

题目

给定实数 x 和整数 n，计算 $x^{n}$ ，且不能调用语言内置的幂函数。要求使用递归分治：每次把指数缩小一半，并复用已经算出的子问题结果。本题规定 $x^{0} = 1$ （包括 x = 0 时）；当 n < 0 时保证 x != 0，答案可转化为 $(1/x)^{-n}$ 。

解题提示（继承自原文档）

n 等于 0 时答案是 1；
算出 x 的 n // 2 次方后保存为 half，不要递归调用第二次；
当 n < 0 时，先把 x 改为 1 / x，再把 n 改为 -n；使用 C++ 或 Java 时，可先把 n 转为 64 位整数，避免最小的 32 位整数取相反数时溢出。

对应 LeetCode 50 题（Pow(x, n)）。注意：常见题解使用迭代位运算，与本练习指定的递归分治方法不同，应依据上述提示完成递归版本。

完整实现

仓库中的 fast_power.py 等实现覆盖了正指数情形（含断言自测）。按本题要求补全负指数分支后的完整版本如下（Python 版）：

def fast_pow(x: float, n: int) -> float:
    """快速幂（递归分治，支持负指数）"""
    if n < 0:
        # 转化为 (1/x)^(-n)
        x, n = 1 / x, -n
    if n == 0:
        # x^0 = 1，包括 x = 0 时
        return 1.0
    half = fast_pow(x, n // 2)   # 分：子问题，只递归一次
    if n % 2 == 0:               # 治：合并子问题的解
        return half * half
    return half * half * x


if __name__ == "__main__":
    assert fast_pow(7, 0) == 1      # x^0 = 1
    assert fast_pow(3, 5) == 243   # 与知识巩固题的推演结果一致
    assert fast_pow(2, 6) == 64
    assert abs(fast_pow(2, -2) - 0.25) < 1e-9  # 负指数：(1/2)^2

语言相关细节与边界

溢出防护（C++ / Java）：当 n 为 Integer.MIN_VALUE（即 $- 2^{31}$ ）时，-n 在 32 位有符号整数下会回绕为自身。因此解题提示第 3 条建议先把 n 提升为 64 位整数（C++ 的 long long、Java 的 long）再做取反。仓库 C++ 实现与 Java 实现目前针对非负指数编写，接入完整题面时需加上该防护。
浮点结果：题目允许 x 为实数，负指数结果一般不是整数，测试时建议用误差范围（如 abs(a - b) < 1e-9）而非精确相等比较。
复杂度：每层只做常数次乘法，递归深度 $\lceil \log_2 n \rceil + 1$ ，故时间复杂度为 $O(\log n)$ ；递归栈帧占用 $O(\log n)$ 空间。

自检清单

完成本题后可用以下要点自查：

fast_pow(7, 0) 是否返回 1（含 x = 0 的情形）；
fast_pow(3, 5) 是否等于 243，与本文第二节的逐层推演一致；
负指数输入是否先被转化为正指数情形再进入递归；
每层是否仅有一次对 fast_pow 的递归调用（对照第三节第 3 问的原理）。

小结

本练习集围绕分治策略的三个层面递进：先用"排序 / 求最大值 / 栈操作序列"三个案例辨析何时该用、何时不该用分治；再通过对 x = 3, n = 5 的完整调用推演，看清快速幂"减半指数 + 复用子问题"如何把 $O (n)$ 连乘压缩到 $O (\log n)$ ；然后以二叉树重建为例，体会分治在"划分索引区间"上的严谨性（对应 build_binary_tree_problem.md 的 $O (n)$ 解法）；最后通过编程题把上述原理落成可运行、带边界与溢出处理的代码。配合 chapter_divide_and_conquer 章节的正文与多语言实现，即可完整掌握分治算法从判断到实现的全流程。