OI-wiki 递归与分治算法全解从递归思维到分治套路【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读本文是 OI-wiki「基础」板块的核心章节系统讲解递归Recursion与分治Divide and Conquer两种基础算法的定义、区别与结合运用。你将掌握递归的「结束条件 自我调用」两大特征、递归与递推的取舍、分治法「分解 → 解决 → 合并」的三步流程并通过归并排序、二叉树遍历、LeetCode 437「路径总和 III」等实例学会用「相信递归函数」的思维方式快速写出优雅代码。文中所有示例均可在本仓库的源码与测试用例中直接验证运行。递归在函数定义中使用函数自身定义递归Recursion在数学和计算机科学中是指在函数的定义中使用函数自身的方法在计算机科学中还额外指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归的基本思想是某个函数直接或者间接地调用自身这样原问题的求解就转换为了许多性质相同但是规模更小的子问题。求解时只需要关注如何把原问题划分成符合条件的子问题而不需要过分关注这个子问题是如何被解决的。引入几个帮助理解的例子要理解递归就得先理解什么是递归一个经典的循环自指玩笑。如何给一堆数字排序答分成两半先排左半边再排右半边最后合并就行了至于怎么排左边和右边请重新阅读这句话。你今年几岁答去年的岁数加一岁1999 年我出生。递归在数学中非常常见。例如集合论对自然数的正式定义是1 是一个自然数每个自然数都有一个后继这一个后继也是自然数。下面这张图通过「搜索『递归』却提示『您是不是要找递归』」的场景直观地展示了递归的自指特性递归代码最重要的两个特征结束条件和自我调用。自我调用是在解决子问题而结束条件定义了最简子问题的答案。任何递归代码都逃不出这个骨架int func(传入数值) { if (终止条件) return 最小子问题解; return func(缩小规模); }为什么要写递归1. 结构清晰可读性强。以归并排序详见归并排序专题为例分别用递归与非递归倍增两种方法实现对比一目了然 Ccpp // 不使用递归的归并排序算法倍增法 template typename T void merge_sort(vectorT a) { int n a.size(); for (int seg 1; seg n; seg seg seg) for (int start 0; start n - seg; start seg seg) merge(a, start, start seg - 1, std::min(start seg seg - 1, n - 1)); } // 使用递归的归并排序算法 template typename T void merge_sort(vectorT a, int front, int end) { if (front end) return; int mid front (end - front) / 2; merge_sort(a, front, mid); merge_sort(a, mid 1, end); merge(a, front, mid, end); } Pythonpython # 不使用递归的归并排序算法 def merge_sort(a): n len(a) seg, start 1, 0 while seg n: while start n - seg: merge(a, start, start seg - 1, min(start seg seg - 1, n - 1)) start start seg seg seg seg seg # 使用递归的归并排序算法 def merge_sort(a, front, end): if front end: return mid front (end - front) / 2 merge_sort(a, front, mid) merge_sort(a, mid 1, end) merge(a, front, mid, end) 显然递归版本比非递归版本更易理解。递归版本的做法一目了然把左半边排序把右半边排序最后合并两边。而非递归版本看起来不知所云充斥着各种难以理解的边界计算细节例如段长seg的翻倍、起始位置的seg seg步进、min兜底右边界特别容易出 bug且难以调试。2. 练习分析问题的结构。当发现问题可以被分解成相同结构的小问题时递归写多了就能敏锐发现这个特点进而高效解决问题。递归的缺点在程序执行中递归是利用堆栈来实现的。每当进入一个函数调用栈就会增加一层栈帧每次函数返回栈就会减少一层栈帧。而栈不是无限大的当递归层数过多时就会造成栈溢出的后果。显然有时候递归处理是高效的比如归并排序有时候是低效的比如数孙悟空身上的毛因为堆栈会消耗额外空间而简单的递推不会消耗空间。比如这个例子给一个链表头计算它的长度// 典型的递推遍历框架 int size(Node *head) { int size 0; for (Node *p head; p ! nullptr; p p-next) size; return size; } // 我就是要写递归递归天下第一 int size_recursion(Node *head) { if (head nullptr) return 0; return size_recursion(head-next) 1; }对这两种实现做基准测试compiler 设为 Clang 10.0优化设为 O1结果如下——纵轴是 CPU 时间与空操作时间的比值比值越低越快。递归版本约为 6.5e-6非递归版本约为 4e-6可见在这种「无脑遍历一遍」的场景下递归版本因为额外维护调用栈而更慢这个对比告诉我们递归不是银弹。在问题天然具有「分解 → 回溯」结构时排序、树的遍历、搜索递归清晰高效在问题本质是「单遍线性扫描」时遍历链表、数长度递推循环更省空间、更快。递归的优化比较初级的递归实现可能递归次数太多容易超时这时需要对递归进行优化。常见的优化方向搜索优化剪枝在深度优先搜索中通过记忆化搜索、最优性剪枝、可行性剪枝等方式大幅减少无效递归分支是竞赛中最实用的手段。记忆化搜索把递归计算过的状态存下来再次遇到相同状态直接返回记录值避免重复计算。它确保每个状态只访问一次因此也是一种常见的动态规划实现方式属于典型的「用空间换时间」。分治分而治之定义分治Divide and Conquer字面上的解释是「分而治之」把一个复杂的问题分成两个或更多的相同或相似的子问题直到最后子问题可以简单地直接求解原问题的解即子问题的解的合并。过程分治算法的核心思想就是「分而治之」大概的流程可以分为三步分解 → 解决 → 合并分解原问题为结构相同的子问题。分解到某个容易求解的边界之后进行递归求解。将子问题的解合并成原问题的解。分治法能解决的问题一般有如下特征该问题的规模缩小到一定的程度就可以容易地解决该问题可以分解为若干个规模较小的相同问题即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解该问题所分解出的各个子问题是相互独立的即子问题之间不包含公共的子问题。注意如果各子问题是不独立的分治法就要重复地解公共的子问题也就做了许多不必要的工作。此时虽然也可用分治法但一般用动态规划较好。以归并排序理解分治流程以归并排序为例。假设实现归并排序的函数名为merge_sort明确该函数的职责即对传入的一个数组排序。这个问题显然可以分解给一个数组排序等于给该数组的左右两半分别排序然后合并成一个数组。void merge_sort(一个数组) { if (可以很容易处理) return; merge_sort(左半个数组); merge_sort(右半个数组); merge(左半个数组, 右半个数组); }传给它半个数组那么处理完后这半个数组就已经被排好了。注意到merge_sort与二叉树的后序遍历模板极其相似——因为分治算法的套路是分解 → 解决触底→ 合并回溯先左右分解再处理合并回溯就是在退栈即相当于后序遍历。关于merge的两种常用实现方式请参考 docs/basic/merge-sort.md指针式写法可用algorithm库的merge函数为保证排序稳定性合并时应当在前段首元素小于等于后段首元素a[i] b[j]时优先取前段元素。归并排序在最优、最坏与平均情况下时间复杂度均为 $\Theta(n\log n)$空间复杂度为 $\Theta(n)$。写递归的要点**明白一个函数的作用并相信它能完成这个任务千万不要跳进这个函数里面企图探究更多细节**否则就会陷入无穷的细节无法自拔——人脑能压几个栈啊。以遍历二叉树为例void traverse(TreeNode* root) { if (root nullptr) return; traverse(root-left); traverse(root-right); }这几行代码就足以遍历任何一棵二叉树了。对于递归函数traverse(root)只要相信给它一个根节点root它就能遍历这棵树所以只需要把这个节点的左右节点再传给这个函数就行了。同样扩展到遍历一棵 N 叉树与二叉树的写法一模一样不过对于 N 叉树显然没有中序遍历void traverse(TreeNode* root) { if (root nullptr) return; for (auto child : root-children) traverse(child); }这个「递归信任」原则是整篇文档最核心的编程心法写递归时只关心当前函数这一层该做什么、子问题如何划分、边界条件是什么把更深层的求解交给递归本身。区别递归与枚举、递归与分治递归与枚举的区别递归和枚举的区别在于枚举是横向地把问题划分然后依次求解子问题而递归是把问题逐级分解是纵向的拆分。递归与分治的区别递归是一种编程技巧、一种解决问题的思维方式分治算法很大程度上是基于递归的、解决更具体问题的算法思想。换句话说递归是「怎么做」的工具分治是「做什么」的策略。例题详解路径总和 IIILeetCode 437题目给定一个二叉树它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。路径不需要从根节点开始也不需要在叶子节点结束但是路径方向必须是向下的只能从父节点到子节点。二叉树不超过 1000 个节点且节点数值范围是 $[-1000000, 1000000]$ 的整数。示例root [10,5,-3,3,2,null,11,3,-2,null,1], sum 810 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1返回 3。和等于 8 的路径有5 - 35 - 2 - 1-3 - 11题目解析题目看起来很复杂不过代码却极其简洁。首先明确递归求解树的问题必然是要遍历整棵树的所以二叉树的遍历框架分别对左右子树递归调用函数本身必然要出现在主函数pathSum中。那么对于每个节点它们应该干什么呢它们应该看看自己和它们的子树包含多少条符合条件的路径。按照前面说的技巧根据分析来定义清楚每个递归函数应该做的事pathSum函数给定一个节点和一个目标值返回以这个节点为根的树中和为目标值的路径总数count函数给定一个节点和一个目标值返回以这个节点为根的树中能凑出几个以该节点为路径开头、和为目标值的路径总数。int pathSum(TreeNode *root, int sum) { if (root nullptr) return 0; int pathImLeading count(root, sum); // 自己为开头的路径数 int leftPathSum pathSum(root-left, sum); // 左边路径总数相信它能算出来 int rightPathSum pathSum(root-right, sum); // 右边路径总数相信它能算出来 return leftPathSum rightPathSum pathImLeading; } int count(TreeNode *node, int sum) { if (node nullptr) return 0; // 能不能作为一条单独的路径呢 int isMe (node-val sum) ? 1 : 0; // 左边的你那边能凑几个 sum - node.val int leftNode count(node-left, sum - node-val); // 右边的你那边能凑几个 sum - node.val int rightNode count(node-right, sum - node-val); return isMe leftNode rightNode; // 我这能凑这么多个 }还是那句话明白每个函数能做的事并相信它们能够完成。总结一下pathSum函数提供了二叉树遍历框架在遍历中对每个节点调用count函数这里用的是先序遍历不过中序遍历和后序遍历也可以。count函数也是一个二叉树遍历用于寻找以该节点开头的目标值路径。仓库源码与测试验证上述例题在本仓库中有完整的可运行实现与配套测试可以按下面的文件路径直接查看、编译运行数据结构定义divide-and-conquer_1.h定义了二叉树结点TreeNode包含val、left、right三个成员与带初值的构造函数左、右孩子初始化为nullptr。核心算法实现divide-and-conquer_1.cpp给出了count与pathSum的精简实现与文中的注释版完全等价int count(TreeNode *node, int sum) { if (node nullptr) return 0; return (node-val sum) count(node-left, sum - node-val) count(node-right, sum - node-val); } int pathSum(TreeNode *root, int sum) { if (root nullptr) return 0; return count(root, sum) pathSum(root-left, sum) pathSum(root-right, sum); }可执行入口divide-and-conquer_1.aux1.cppmain函数从标准输入读取层序遍历序列null表示空结点MAXN 1000对应题目的节点上限按下标关系建树后调用pathSum输出答案最后释放全部动态分配的结点。仓库还提供了本题的官方输入输出样例可直接用于自测输入 divide-and-conquer_1.in第一行是节点数11第二行是层序序列10 5 -3 3 2 null 11 3 -2 null 1第三行是目标和8期望输出 divide-and-conquer_1.ans答案为3与题目示例一致。将输入重定向到编译好的程序即可验证./main divide-and-conquer_1.in程序应输出3。习题推荐LeetCode 上的递归专题练习Recursion ILeetCode 上的分治算法专项练习Divide and Conquer 标签。建议按「先递归后分治」的顺序刷题先用递归专题打牢「结束条件 自我调用」的基本功再用分治专题体会「分解 → 解决 → 合并」的套路在不同问题排序、最大子段和、最近点对、快速幂等中的迁移应用。参考资料与注释labuladong 的算法小抄 - 递归详解本文递归优化部分的重要参考。本文相关源码与测试docs/basic/code/divide-and-conquer/与docs/basic/examples/divide-and-conquer/。递归优化的延伸阅读搜索优化剪枝、记忆化搜索。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 OI-wiki 递归与分治算法全解：从递归思维到分治套路
OI-wiki 递归与分治算法全解从递归思维到分治套路【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读本文是 OI-wiki「基础」板块的核心章节系统讲解递归Recursion与分治Divide and Conquer两种基础算法的定义、区别与结合运用。你将掌握递归的「结束条件 自我调用」两大特征、递归与递推的取舍、分治法「分解 → 解决 → 合并」的三步流程并通过归并排序、二叉树遍历、LeetCode 437「路径总和 III」等实例学会用「相信递归函数」的思维方式快速写出优雅代码。文中所有示例均可在本仓库的源码与测试用例中直接验证运行。递归在函数定义中使用函数自身定义递归Recursion在数学和计算机科学中是指在函数的定义中使用函数自身的方法在计算机科学中还额外指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归的基本思想是某个函数直接或者间接地调用自身这样原问题的求解就转换为了许多性质相同但是规模更小的子问题。求解时只需要关注如何把原问题划分成符合条件的子问题而不需要过分关注这个子问题是如何被解决的。引入几个帮助理解的例子要理解递归就得先理解什么是递归一个经典的循环自指玩笑。如何给一堆数字排序答分成两半先排左半边再排右半边最后合并就行了至于怎么排左边和右边请重新阅读这句话。你今年几岁答去年的岁数加一岁1999 年我出生。递归在数学中非常常见。例如集合论对自然数的正式定义是1 是一个自然数每个自然数都有一个后继这一个后继也是自然数。下面这张图通过「搜索『递归』却提示『您是不是要找递归』」的场景直观地展示了递归的自指特性递归代码最重要的两个特征结束条件和自我调用。自我调用是在解决子问题而结束条件定义了最简子问题的答案。任何递归代码都逃不出这个骨架int func(传入数值) { if (终止条件) return 最小子问题解; return func(缩小规模); }为什么要写递归1. 结构清晰可读性强。以归并排序详见归并排序专题为例分别用递归与非递归倍增两种方法实现对比一目了然 Ccpp // 不使用递归的归并排序算法倍增法 template typename T void merge_sort(vectorT a) { int n a.size(); for (int seg 1; seg n; seg seg seg) for (int start 0; start n - seg; start seg seg) merge(a, start, start seg - 1, std::min(start seg seg - 1, n - 1)); } // 使用递归的归并排序算法 template typename T void merge_sort(vectorT a, int front, int end) { if (front end) return; int mid front (end - front) / 2; merge_sort(a, front, mid); merge_sort(a, mid 1, end); merge(a, front, mid, end); } Pythonpython # 不使用递归的归并排序算法 def merge_sort(a): n len(a) seg, start 1, 0 while seg n: while start n - seg: merge(a, start, start seg - 1, min(start seg seg - 1, n - 1)) start start seg seg seg seg seg # 使用递归的归并排序算法 def merge_sort(a, front, end): if front end: return mid front (end - front) / 2 merge_sort(a, front, mid) merge_sort(a, mid 1, end) merge(a, front, mid, end) 显然递归版本比非递归版本更易理解。递归版本的做法一目了然把左半边排序把右半边排序最后合并两边。而非递归版本看起来不知所云充斥着各种难以理解的边界计算细节例如段长seg的翻倍、起始位置的seg seg步进、min兜底右边界特别容易出 bug且难以调试。2. 练习分析问题的结构。当发现问题可以被分解成相同结构的小问题时递归写多了就能敏锐发现这个特点进而高效解决问题。递归的缺点在程序执行中递归是利用堆栈来实现的。每当进入一个函数调用栈就会增加一层栈帧每次函数返回栈就会减少一层栈帧。而栈不是无限大的当递归层数过多时就会造成栈溢出的后果。显然有时候递归处理是高效的比如归并排序有时候是低效的比如数孙悟空身上的毛因为堆栈会消耗额外空间而简单的递推不会消耗空间。比如这个例子给一个链表头计算它的长度// 典型的递推遍历框架 int size(Node *head) { int size 0; for (Node *p head; p ! nullptr; p p-next) size; return size; } // 我就是要写递归递归天下第一 int size_recursion(Node *head) { if (head nullptr) return 0; return size_recursion(head-next) 1; }对这两种实现做基准测试compiler 设为 Clang 10.0优化设为 O1结果如下——纵轴是 CPU 时间与空操作时间的比值比值越低越快。递归版本约为 6.5e-6非递归版本约为 4e-6可见在这种「无脑遍历一遍」的场景下递归版本因为额外维护调用栈而更慢这个对比告诉我们递归不是银弹。在问题天然具有「分解 → 回溯」结构时排序、树的遍历、搜索递归清晰高效在问题本质是「单遍线性扫描」时遍历链表、数长度递推循环更省空间、更快。递归的优化比较初级的递归实现可能递归次数太多容易超时这时需要对递归进行优化。常见的优化方向搜索优化剪枝在深度优先搜索中通过记忆化搜索、最优性剪枝、可行性剪枝等方式大幅减少无效递归分支是竞赛中最实用的手段。记忆化搜索把递归计算过的状态存下来再次遇到相同状态直接返回记录值避免重复计算。它确保每个状态只访问一次因此也是一种常见的动态规划实现方式属于典型的「用空间换时间」。分治分而治之定义分治Divide and Conquer字面上的解释是「分而治之」把一个复杂的问题分成两个或更多的相同或相似的子问题直到最后子问题可以简单地直接求解原问题的解即子问题的解的合并。过程分治算法的核心思想就是「分而治之」大概的流程可以分为三步分解 → 解决 → 合并分解原问题为结构相同的子问题。分解到某个容易求解的边界之后进行递归求解。将子问题的解合并成原问题的解。分治法能解决的问题一般有如下特征该问题的规模缩小到一定的程度就可以容易地解决该问题可以分解为若干个规模较小的相同问题即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解该问题所分解出的各个子问题是相互独立的即子问题之间不包含公共的子问题。注意如果各子问题是不独立的分治法就要重复地解公共的子问题也就做了许多不必要的工作。此时虽然也可用分治法但一般用动态规划较好。以归并排序理解分治流程以归并排序为例。假设实现归并排序的函数名为merge_sort明确该函数的职责即对传入的一个数组排序。这个问题显然可以分解给一个数组排序等于给该数组的左右两半分别排序然后合并成一个数组。void merge_sort(一个数组) { if (可以很容易处理) return; merge_sort(左半个数组); merge_sort(右半个数组); merge(左半个数组, 右半个数组); }传给它半个数组那么处理完后这半个数组就已经被排好了。注意到merge_sort与二叉树的后序遍历模板极其相似——因为分治算法的套路是分解 → 解决触底→ 合并回溯先左右分解再处理合并回溯就是在退栈即相当于后序遍历。关于merge的两种常用实现方式请参考 docs/basic/merge-sort.md指针式写法可用algorithm库的merge函数为保证排序稳定性合并时应当在前段首元素小于等于后段首元素a[i] b[j]时优先取前段元素。归并排序在最优、最坏与平均情况下时间复杂度均为 $\Theta(n\log n)$空间复杂度为 $\Theta(n)$。写递归的要点**明白一个函数的作用并相信它能完成这个任务千万不要跳进这个函数里面企图探究更多细节**否则就会陷入无穷的细节无法自拔——人脑能压几个栈啊。以遍历二叉树为例void traverse(TreeNode* root) { if (root nullptr) return; traverse(root-left); traverse(root-right); }这几行代码就足以遍历任何一棵二叉树了。对于递归函数traverse(root)只要相信给它一个根节点root它就能遍历这棵树所以只需要把这个节点的左右节点再传给这个函数就行了。同样扩展到遍历一棵 N 叉树与二叉树的写法一模一样不过对于 N 叉树显然没有中序遍历void traverse(TreeNode* root) { if (root nullptr) return; for (auto child : root-children) traverse(child); }这个「递归信任」原则是整篇文档最核心的编程心法写递归时只关心当前函数这一层该做什么、子问题如何划分、边界条件是什么把更深层的求解交给递归本身。区别递归与枚举、递归与分治递归与枚举的区别递归和枚举的区别在于枚举是横向地把问题划分然后依次求解子问题而递归是把问题逐级分解是纵向的拆分。递归与分治的区别递归是一种编程技巧、一种解决问题的思维方式分治算法很大程度上是基于递归的、解决更具体问题的算法思想。换句话说递归是「怎么做」的工具分治是「做什么」的策略。例题详解路径总和 IIILeetCode 437题目给定一个二叉树它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。路径不需要从根节点开始也不需要在叶子节点结束但是路径方向必须是向下的只能从父节点到子节点。二叉树不超过 1000 个节点且节点数值范围是 $[-1000000, 1000000]$ 的整数。示例root [10,5,-3,3,2,null,11,3,-2,null,1], sum 810 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1返回 3。和等于 8 的路径有5 - 35 - 2 - 1-3 - 11题目解析题目看起来很复杂不过代码却极其简洁。首先明确递归求解树的问题必然是要遍历整棵树的所以二叉树的遍历框架分别对左右子树递归调用函数本身必然要出现在主函数pathSum中。那么对于每个节点它们应该干什么呢它们应该看看自己和它们的子树包含多少条符合条件的路径。按照前面说的技巧根据分析来定义清楚每个递归函数应该做的事pathSum函数给定一个节点和一个目标值返回以这个节点为根的树中和为目标值的路径总数count函数给定一个节点和一个目标值返回以这个节点为根的树中能凑出几个以该节点为路径开头、和为目标值的路径总数。int pathSum(TreeNode *root, int sum) { if (root nullptr) return 0; int pathImLeading count(root, sum); // 自己为开头的路径数 int leftPathSum pathSum(root-left, sum); // 左边路径总数相信它能算出来 int rightPathSum pathSum(root-right, sum); // 右边路径总数相信它能算出来 return leftPathSum rightPathSum pathImLeading; } int count(TreeNode *node, int sum) { if (node nullptr) return 0; // 能不能作为一条单独的路径呢 int isMe (node-val sum) ? 1 : 0; // 左边的你那边能凑几个 sum - node.val int leftNode count(node-left, sum - node-val); // 右边的你那边能凑几个 sum - node.val int rightNode count(node-right, sum - node-val); return isMe leftNode rightNode; // 我这能凑这么多个 }还是那句话明白每个函数能做的事并相信它们能够完成。总结一下pathSum函数提供了二叉树遍历框架在遍历中对每个节点调用count函数这里用的是先序遍历不过中序遍历和后序遍历也可以。count函数也是一个二叉树遍历用于寻找以该节点开头的目标值路径。仓库源码与测试验证上述例题在本仓库中有完整的可运行实现与配套测试可以按下面的文件路径直接查看、编译运行数据结构定义divide-and-conquer_1.h定义了二叉树结点TreeNode包含val、left、right三个成员与带初值的构造函数左、右孩子初始化为nullptr。核心算法实现divide-and-conquer_1.cpp给出了count与pathSum的精简实现与文中的注释版完全等价int count(TreeNode *node, int sum) { if (node nullptr) return 0; return (node-val sum) count(node-left, sum - node-val) count(node-right, sum - node-val); } int pathSum(TreeNode *root, int sum) { if (root nullptr) return 0; return count(root, sum) pathSum(root-left, sum) pathSum(root-right, sum); }可执行入口divide-and-conquer_1.aux1.cppmain函数从标准输入读取层序遍历序列null表示空结点MAXN 1000对应题目的节点上限按下标关系建树后调用pathSum输出答案最后释放全部动态分配的结点。仓库还提供了本题的官方输入输出样例可直接用于自测输入 divide-and-conquer_1.in第一行是节点数11第二行是层序序列10 5 -3 3 2 null 11 3 -2 null 1第三行是目标和8期望输出 divide-and-conquer_1.ans答案为3与题目示例一致。将输入重定向到编译好的程序即可验证./main divide-and-conquer_1.in程序应输出3。习题推荐LeetCode 上的递归专题练习Recursion ILeetCode 上的分治算法专项练习Divide and Conquer 标签。建议按「先递归后分治」的顺序刷题先用递归专题打牢「结束条件 自我调用」的基本功再用分治专题体会「分解 → 解决 → 合并」的套路在不同问题排序、最大子段和、最近点对、快速幂等中的迁移应用。参考资料与注释labuladong 的算法小抄 - 递归详解本文递归优化部分的重要参考。本文相关源码与测试docs/basic/code/divide-and-conquer/与docs/basic/examples/divide-and-conquer/。递归优化的延伸阅读搜索优化剪枝、记忆化搜索。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考