分治算法
分治,"分而治之"。从字面上理解就是分---治，把大的问题分成小问题，解决一个一个小问题，之后把问题的答案合并起来，就得到大问题的结果。您肯定会在想，这思想这么简单，你不说我也是知道。历史上，秦国通过远交近攻的策略，逐个击破，最后统一六国不也是分治思想的体现吗？
以下用一个二叉树的前序遍历为例，对分治思想在代码上的体现进行说明。
public class PreoderTraversal {
public class TreeNode{
private int val;
public TreeNode left,right;
public TreeNode(int val){
this.val = val;
this.left = this.right = null;
}
}
public ArrayList<Integer> preodertraversal(TreeNode root){
ArrayList<Integer> result = new ArrayList<Integer>();
//退出的条件
if(root == null){
return null;
}
//分：左子树与右子树
ArrayList<Integer> left = preodertraversal(root.left);
ArrayList<Integer> right = preodertraversal(root.right);
//治：把得到的结果合并起来
result.add(root.val);
result.addAll(left);
result.addAll(right);
return result;
}
}
上面的过程可以通过一个递推公式来表示
T(n) = 2T(2/n)+O(1)
2T(2/n) 表示 原来的大问题变成两个原来一半的问题
O(1)表示 对二叉树的每个节点只操作一次。
上面的公式可以推出 上面前序遍历的时间复杂度是 O(n)
从以上代码，可以看出，分治算法在代码实现上有以下两点好处：
1.前序遍历的结果可用通过一个函数内的ArrayList返回不需要创建全局变量，来存放结果。
2.对于拆分后的问题，运算量大，采用多并发，多核来处理，也是很容易的。具体结合上面代码来说，对于left、right结果求解，可以分别启用一个线程。
两道题
对于分治的题目很多，为什么选择下面这两道题目呢？因为足够典型，学会了这两道题，我们保证，您在与同事、面试官聊起分治算法的时候，他们会认为您是懂分治算法。
- 接下来祭出第一道题目
分析：
既然我们使用分治来解决，那就看看问题怎么拆分呢？
这道题目中是求两个节点的公共的祖先，很显然，问题的拆分可以依据：两个节点在二叉树的位置来拆分问题：
都在左子树上、都在右子树上、一个边一个、有一个节点就是根节点
一个大的问题拆分四个问题，逐个解决，求出大问题，下面给出 实现代码
public TreeNode getAncestor(TreeNode root,TreeNode node1,TreeNode node2){
if (root == null)
{
return null;
}
//如果有一个节点就是根节点
if(root == node1 || root == node2){
return root;
}
TreeNode left = getAncestor(root.left,node1,node2);
TreeNode right = getAncestor(root.right,node1,node2);
//节点一边一个
if(left == null && right == null)
{
return root;
}
//节点都在左子树
if (left != null) {
return left;
}
//节点都在右子树
if (right != null) {
return right;
}
return null;
}
如果您还不太明白，没关系，对着分析和代码多看几次，就会打通任督二脉的。
- 第二道（这道题，有点小难度）
为什么说这道题有点难度呢？原因在于二叉树上有负值的存在。而且最关键的是题目只是说遍历二叉树，求最大和，并没有说是从哪里出发，如果从根出发就是求：
root---->anyNode 根到任意节点的最大和
明显这题目的意思是
anyNode---->anyNode 任意节点到任意节点的最大和。
采用分治，怎么拆分呢？
为三种情况：左子树、右子树、左子树-->根-->右子树。不明白，没关系，看下图分析。
分析：
代码实现
public class returnType{
int root2any,any2any;
returnType(int root2any,int any2any){
this.root2any = root2any; //存放上面分析的root-->anyNode
this.any2any = any2any; // anyNode-->anyNode
}
}
public returnType maxSum(TreeNode root){
//如果二叉树不存在，直接设置成最小值
if(root == null){
return new returnType(Integer.MIN_VALUE,Integer.MIN_VALUE);
}
returnType left = maxSum(root.left);
returnType right = maxSum(root.right);
//结合上面的图就是求A+B大还是A+C大呢，
和0做比较就是因为有负数的存在
int root2any =Math.max(0,Math.max(left.root2any,right.root2any))+root.val;
//R=Math.max（D，E）
int any2any = Math.max(left.any2any,right.any2any);
//Math.max(R,A+B+C)
any2any = Math.max(any2any,Math.max(0,left.root2any)+Math.max(0,right.root2any)+ root.val);
return new returnType(root2any,any2any);
}
小福利
分治算法其实在最初的快排和归并排序都接触过了，如果你上面两道题目都理解，下面给出归并排序和快排的代码在重温一下，看下感觉是不是so easy！！
归并排序
private static Comparable[] aux;
public static void sort(Comparable[] list){
aux = new Comparable[list.length];
sort(list,0,list.length-1);
}
public static void sort(Comparable[] list,int lo,int hi){
if(lo < hi){
return;
}
int mid = lo +(hi-lo)/2;
//分
sort(list,lo,mid);
sort(list,mid+1,hi);
//治
meger(list,lo,mid,hi); //这个是归并的具体具体过程，我们这篇介绍分治的重点，在此忽略了
}
快速排序
public static void sort(Comparable[] list){
Collections.shuffle(list); //消除输入的影响
sort(list,0,list.length-1);
}
public static void sort(Comparable[] list,int lo,int hi){
if(lo < hi){
return;
}
int j = patition(list,lo,hi); //快排中重要的切分，典型有三取样切分。找出大小为中间的点
在此忽略了具体实现，有兴趣看相关资料
//分
sort(list,lo,j-1);
sort(list,j+1,hi);
}
快排和归并排序的可以归纳的递推公式
T(n) = 2T(2/n) +O(n)
时间复杂度是 ）O(NlogN)
