分而治之

分而治之是算法设计的一种方法。

它将一个问题分成多个和原问题相似的小问题，递归解决小问题，再将结果合并以解决原来的问题。

场景一：归并排序

分：将数组一份为二； 解：递归的对两个子数组进行归并排序； 合：合并有序子数组；

	Array.prototype.mergSort = function(){
	    const rec = (arr) => {
	        //分
	        if(arr.length === 1){ return arr; };
	        const mid = Math.floor(arr.length / 2);
	        const left = arr.slice(0, mid);
	        const right = arr.slice(mid, arr.length);
	        const orderLeft = rec(left);
	        const orderRight = rec(right);
	        //合
	        const res = [];
	        while(orderLeft.length || orderRight.length){
	            if(orderLeft.length && orderRight.length){
	                res.push( orderLeft[0] < orderRight[0] ? orderLeft.shift() :  orderRight.shift() );
	            }else if(orderLeft.length){
	                res.push(orderLeft.shift());
	            }else if(orderRight.length){
	                res.push(orderRight.shift());
	            }
	        }
	        return res;
	    }
	    const res = rec(this);
	    res.forEach((n, i) => {this[i] = n;});
	}
	var arr = [6,1,8,5,7,4,2,3];
	arr.mergSort();

场景二：快速排序

分：选基准，按基准将数组分过程两个子数组； 解：递归地对子数组进行快速排序； 合：对子数组进行合并；

		Array.prototype.quickSort = function(){
	    const rec = (arr) => {
	        if(arr.length === 1 || arr.length === 0){ return arr;}
	        const left = [];
	        const right = [];
	        const mid = arr[0];
	        for(let i = 1; i < arr.length; i++){
	            if(arr[i] > mid){
	                right.push(arr[i]);
	            }else{
	                left.push(arr[i]);
	            }
	        }
	        return [...rec(left), mid, ...rec(right)];
	    };
	    const res = rec(this);
	    //将res拷贝到this
	    res.forEach( (n, i) => { this[i] = n; });
	} 

例题一：猜数字大小

var guessNumber = function(n) {
    const rec = (low, high) => {
        if(low > high){ return; }
        const mid = Math.floor((low + high) / 2);
        const res = guess(mid);
        if(res === 0){
            return mid;
        }else if( res === 1){
            return rec(mid+1, high);
        }else{
            return rec(low, mid-1);
        }
    }
    return rec(1, n);
};

例题二：翻转二叉树

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    if(!root) { return null;}
    return {
        val: root.val, 
        left: invertTree(root.right),
        right: invertTree(root.left)
    }
};

例题三：相同的树

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if(!p && !q){ return true;}
    if(p && q && p.val == q.val &&
    isSameTree(q.left, p.left) &&
    isSameTree(q.right, p.right)){
        return true;
    }
    return false;
};

例题四：对称二叉树

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if(!root) return true; 
    const rec = (l, r) => { 
        if(!l && !r) return true; 
        if(l && r && l.val === r.val &&
        rec(l.right, r.left) &&
        rec(l.left, r.right)){
            return true;
        }
        return false;
    }
    return rec(root.left, root.right)
};