概述
步骤
- Divide(分解) => 将问题划分为一些子问题，子问题的形式和原问题一样，只是规模更小
- Conquer(解决) => 递归地求解子问题。如果子问题规模足够小，则停止递归，直接求解
- Combine(合并) => 将子问题的解组合成原问题的解
注意点
- 分治问题是什么？
- 子问题和原问题的关系是什么？
二叉树
二叉树分治法模板
public class DivideAndConquer {
public Result divideAndConquer(TreeNode root) {
if (root == null) {
// doSomething
return null;
}
Result leftResult = divideAndConquer(root.left);
Result rightResult = divideAndConquer(root.right);
return conbine(leftResult, rightResult);
}
}
分治法 vs 遍历法
- 都利用递归的思想
- 均属于广义 DFS
- 分治法可通过函数返回值得到答案
- 遍历法常常需要全局变量 => 注意值传递，需要声明全局变量
