2 Divide and Conquer

定义

分治法（Divide & Conquer Algorithm）是说将一个大问题，拆分为2个或者多个小问题，当小问题得到结果之后，合并他们的结果来得到大问题的结果。

举一个例子，比如中国要进行人口统计。那么如果使用遍历（Traversal）的办法，做法如下：

人口普查员小张自己一个人带着一个本子，跑遍全中国挨家挨户的敲门查户口

而如果使用分治法，做法如下：

1. 国家统计局的老板小李想要知道全国人口的总数，于是他找来全国各个省的统计局领导，下派人口普查任务给他们，让他们各自去统计自己省的人口总数。在小李这儿，他只需要最后将各个省汇报的人口总数结果累加起来，就得到了全国人口的数目。

2. 然后每个省的领导，又找来省里各个市的领导，让各个市去做人口统计。

3. 市找县，县找镇，镇找乡。最后乡里的干部小王挨家挨户敲门去查户口。

在这里，把全国的任务拆分为省级的任务的过程，就是分治法中分的这个步骤。把各个小任务派发给别人去完成的过程，就是分治法中治的这个步骤。但是事实上我们还有第三个步骤，就是将小任务的结果合并到一起的过程，合这个步骤。因此如果我来取名字的话，我会叫这个算法：分治合算法。

为什么二叉树的问题适合使用分治法？

在一棵二叉树（Binary Tree）中，如果将整棵二叉树看做一个大问题的话，那么根节点（Root）的左子树（Left subtree）就是一个小问题，右子树（Right subtree）是另外一个小问题。这是一个天然就帮你完成了“分”这个步骤的数据结构。

联系与区别

联系

分治法（Divide & Conquer）与遍历法（Traverse）是两种常见的递归（Recursion）方法。

分治法解决问题的思路

先让左右子树去解决同样的问题，然后得到结果之后，再整合为整棵树的结果。

遍历法解决问题的思路

通过前序/中序/后序的某种遍历，游走整棵树，通过一个全局变量或者传递的参数来记录这个过程中所遇到的点和需要计算的结果。

两种方法的区别

从程序实现角度分治法的递归函数，通常有一个返回值，遍历法通常没有。