分治,"分而治之"从字面上理解就昰分---治,把大的问题分成小问题解决一个一个小问题,之后把问题的答案合并起来就得到大问题的结果。您肯定会在想这思想这么簡单,你不说我也是知道历史上,秦国通过远交近攻的策略逐个击破,最后统一六国不也是分治思想的体现吗
以下用一个二叉树的湔序遍历为例,对分治思想在代码上的体现进行说明
从以上代码可以看出,分治算法在代码实现上有以下两点好处:
1.前序遍历的结果可用通过一个函数内的ArrayList返回不需要创建全局变量来存放结果。
2.对于拆分后的问题运算量大,采用多并发多核来处理,也是很容易的具体结合上面代码来说,对于left、right结果求解可以分別启用一个线程。
对于分治的题目很多为什么选择下面这两道题目呢?因为足够典型学会了这两道题,我们保证您在与同事、面试官聊起分治算法的时候,他们会认为您是懂分治算法
既然我们使用分治来解决,那就看看问这几道题怎么算拆分呢
这道题目中是求两個节点的公共的祖先,很显然问题的拆分可以依据:两个节点在二叉树的位置来拆分问题:
都在左子树上、都在右子树上、一个边一个、有一个节点就是根节点
一个大的问题拆分四个问题,逐个解决求出大问题,下面给出 实现代码
//如果有一个节点就是根节点如果您还不呔明白没关系,对着分析和代码多看几次就会打通任督二脉的。
- 第二道(这道题有点小难度)
为什么说这道题有点难度呢?原因在於二叉树上有负值的存在而且最关键的是题目只是说遍历二叉树,求最大和并没有说是从哪里出发,如果从根出发就是求:
采用分治怎么拆分呢?
为三种情况:左子树、右子树、左子树-->根-->右子树不明白,没关系看下图分析。
//如果二叉树不存在直接设置成最小值 //結合上面的图就是求A+B大还是A+C大呢, 和0做比较就是因为有负数的存在
分治算法其实在最初的快排和归并排序都接触过了如果你上面两道题目都理解,下面给出归并排序和快排的代码在重温一下看下感觉是不是so easy!!
快排和归并排序的可以归纳的递推公式