CS-Notes 分治算法题解精读：用两道 Leetcode 经典题掌握「分解、求解、合并」

CS-Notes 分治算法题解精读：用两道 Leetcode 经典题掌握「分解、求解、合并」

【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes

本篇基于 CS-Notes 仓库中 Leetcode 题解 - 分治 一文展开，围绕分治思想在算法题中的落地方式，完整讲解两道中等难度经典题——Leetcode 241「给表达式加括号」与 Leetcode 95「不同的二叉搜索树」的完整 Java 解法，并结合仓库内 数值的整数次方 等题解印证分治思想的通用范式。读完本篇，你能掌握「划分问题 → 递归求解子问题 → 合并子问题解」三步法，并能独立完成分治类题目的复杂度分析与代码实现。

什么是分治：三步范式

分治（Divide and Conquer）的核心在于把一个规模为 N 的原问题，拆成若干个规模更小的同类子问题，对子问题递归求解后，再把子问题的解合并成原问题的解。以 CS-Notes 仓库 算法 - 算法分析 等笔记为参照，分治的三步范式可以概括为：

1. Divide（分解）：将原问题划分为若干规模更小、相互独立的同类子问题；
2. Conquer（求解）：递归地解决各子问题，直到子问题小到可以直接求解（即到达递归基）；
3. Combine（合并）：将子问题的解组合起来，得到原问题的解。

时间复杂度通常取决于「子问题个数 × 每个子问题规模」与「合并开销」，满足主定理情形时多为 O(N log N) 或 O(log N)。

下面两题分别体现了分治在「字符串表达式求值」与「树的递归构造」两个场景中的典型应用，也是仓库原文档的全部内容主体。

题一：给表达式加括号（Leetcode 241）

Different Ways to Add Parentheses (Medium)

题目要求：给定一个仅包含+、-、*运算符号和非负整数的表达式字符串，计算该表达式所有可能的括号添加方式对应的运算结果。

原文档给出的示例：

Input: "2-1-1". ((2-1)-1) = 0 (2-(1-1)) = 2 Output : [0, 2]

分治思路：以运算符为分割点

这道题的关键观察是：任一运算符都可以作为「最后一步运算」的运算符。以 "2-1-1" 中第一个-为界，表达式被划分成左子表达式 "2" 和右子表达式 "1-1"，而左、右两侧各自又是一个规模更小的同类子问题（可以再加括号的表达式）。于是：

• Divide：遍历字符串，每遇到一个运算符，就在其两侧把表达式切分成两个子串；
• Conquer：对左右两个子串递归调用同一函数，得到左右两侧各自所有可能的运算结果列表；
• Combine：用当前运算符把左侧每个结果与右侧每个结果做两两组合运算，得到的值全部加入答案列表。

递归基：当子串中不再包含运算符（ways.size() == 0）时，说明子串就是一个完整的数字，直接Integer.valueOf(input)返回。

完整代码

以下代码完整继承自仓库原文档：

public List<Integer> diffWaysToCompute(String input) { List<Integer> ways = new ArrayList<>(); for (int i = 0; i < input.length(); i++) { char c = input.charAt(i); if (c == '+' || c == '-' || c == '*') { List<Integer> left = diffWaysToCompute(input.substring(0, i)); List<Integer> right = diffWaysToCompute(input.substring(i + 1)); for (int l : left) { for (int r : right) { switch (c) { case '+': ways.add(l + r); break; case '-': ways.add(l - r); break; case '*': ways.add(l * r); break; } } } } } if (ways.size() == 0) { ways.add(Integer.valueOf(input)); } return ways; }

代码解读

• for (int i = 0; i < input.length(); i++)逐字符扫描，仅当c是+、-、*时才把它视为候选分割点；数字部分（含多位数）不会被误切分。
• input.substring(0, i)与input.substring(i + 1)分别取出运算符左侧、右侧子串，递归得到left、right两个结果列表——这就是「Divide + Conquer」。
• 双重for循环遍历左右结果的所有组合，switch (c)按运算符类型做合并——这就是「Combine」。
• 末尾的if (ways.size() == 0)是递归基的判定：没有任何运算符被处理过，说明当前子串是纯数字，将其转为整数放入列表返回，避免空列表向上层传播。

以 "2-1-1" 为例，两个-各作为分割点：第一个-得到左 {2}、右 {0, 2}，合并得 {2, 4}……注意第二个分割点2-(1-1)中的右侧 "1-1" 还会再递归一次得到 {0, 2}，最终合并出 {0, 2}，与示例输出一致。

题二：不同的二叉搜索树（Leetcode 95）

Unique Binary Search Trees II (Medium)

题目要求：给定一个数字 n，生成所有值为 1...n 的二叉搜索树（BST）。BST 性质决定了「根为 i 时，左子树只能由 [s, i-1] 构成，右子树只能由 [i+1, e] 构成」，天然适合分治。

原文档给出的示例：

Input: 3 Output: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ]

对应 n = 3 时的 5 棵不同 BST：

1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3

分治思路：枚举根节点

对闭区间 [s, e] 内的每个值 i 依次充当根节点：

• Divide：左子问题为生成 [s, i-1] 上所有 BST，右子问题为生成 [i+1, e] 上所有 BST；
• Conquer：递归生成左右两侧的候选子树列表；
• Combine：左子树列表与右子树列表做笛卡尔积，每一对 (left, right) 接到新根节点 i 的左右孩子上，构成一棵完整的 BST 加入结果集。

递归基：当s > e（区间为空）时，表示该侧没有节点，返回一个包含null的列表。用「列表里放一个 null」而不是直接返回空列表，是为了让笛卡尔积循环能正常进行——空子树也是一种合法的「选择」。

完整代码

以下代码完整继承自仓库原文档：

public List<TreeNode> generateTrees(int n) { if (n < 1) { return new LinkedList<TreeNode>(); } return generateSubtrees(1, n); } private List<TreeNode> generateSubtrees(int s, int e) { List<TreeNode> res = new LinkedList<TreeNode>(); if (s > e) { res.add(null); return res; } for (int i = s; i <= e; ++i) { List<TreeNode> leftSubtrees = generateSubtrees(s, i - 1); List<TreeNode> rightSubtrees = generateSubtrees(i + 1, e); for (TreeNode left : leftSubtrees) { for (TreeNode right : rightSubtrees) { TreeNode root = new TreeNode(i); root.left = left; root.right = right; res.add(root); } } } return res; }

代码解读

• 入口generateTrees(n)只做 n < 1 的边界处理，随后把 [1, n] 的生成任务委托给私有方法generateSubtrees(s, e)，后者是真正承载分治逻辑的递归函数——这种「公开入口 + 区间递归」的写法是分治题的常见骨架。
• for (int i = s; i <= e; ++i)枚举根节点，每换一个 i，左右子区间的划分随之改变，对应「以 i 为根」这一类解。
• 双重循环for (TreeNode left : leftSubtrees) for (TreeNode right : rightSubtrees)完成左右子树的笛卡尔积合并，每个组合都new TreeNode(i)新建根节点，保证输出的是 n 棵结构独立的树而不是共享节点。
• 复杂度层面，n = 3 时共输出 5 棵树（Catalan 数 C₃），递归状态数为 O(n²) 个区间，总开销随 Catalan 序列增长。

值得一提的是，仓库中 Leetcode 题解 - 树 开头即点明「树是一种递归结构，很多树的问题可以使用递归来处理」——95 题正是这一论断在分治视角下的典型实例：树问题的递归与分治的递归在此完全同构。

同一思想的印证：剑指 Offer 16「数值的整数次方」

仓库 剑指 Offer 题解 - 目录 在「分治」分类下收录了 16. 数值的整数次方，它展示了分治在「无合并结构、只有规模折半」场景中的形态，可作为上面两题的补充印证。

其思路：求 x 的 n 次方，直接连乘是 O(N)；利用乘法可交换性把 n 次乘拆成两半(x^...x) * (x^...x)，两半相同只需算一次，对拆出来的子问题继续拆，子问题规模减半后再平方合并即可。原文档中的核心递归实现：

public double Power(double x, int n) { boolean isNegative = false; if (n < 0) { n = -n; isNegative = true; } double res = pow(x, n); return isNegative ? 1 / res : res; } private double pow(double x, int n) { if (n == 0) return 1; if (n == 1) return x; double res = pow(x, n / 2); res = res * res; if (n % 2 != 0) res *= x; return res; }

每次递归 n 减半、返回时平方合并，时间复杂度从 O(N) 降为 O(log N)——「Divide（n 折半）+ Conquer（递归 pow(x, n/2)）+ Combine（平方，奇数再乘一个 x）」与前述两题的节奏完全一致，只是合并操作退化为一次乘法。

小结与延伸阅读

题目	Divide	Conquer	Combine	关键细节
Leetcode 241 给表达式加括号	以每个运算符切分左右子串	递归求左右两侧所有结果	两两组合做 + / - / *	纯数字子串即递归基
Leetcode 95 不同的二叉搜索树	枚举 i ∈ [s, e] 为根	递归生成 [s, i-1]、[i+1, e] 子树	左右子树笛卡尔积接根	s > e 时返回含 null 的列表
剑指 16 数值的整数次方	n 折半为 n/2	递归求 x^(n/2)	平方，奇数补乘 x	负指数取倒数

从源码结构看，仓库将 Leetcode 与剑指 Offer 两套题解按同一套「算法思想 + 数据结构」分类组织，完整索引见 Leetcode 题解 - 目录，其中分治与双指针、排序、贪心思想、二分查找、搜索、动态规划、数学等思想并列。若你在二分折半、区间划分之外还想练习「递归 + 合并」的写法，可顺带查看 Leetcode 题解 - 树 中的递归系列题目，它们与本文的分治框架互为表里。

【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes