算法设计思想-分而治之

1. 是什么

• 算法设计中的一种方法。
• 将一个问题分成多个和原问题相似的小问题，递归解决小问题，再将结果合并以解决原来的问题。

2. 场景

2.1. 归并排序

• 分：把数组从中间一分为二。
• 解：递归地对两个子数组进行归并排序。
• 合：合并有序子数组。

2.2. 快速排序

• 分：选基准，按基准把数组分成两个子数组。
• 解：递归地对两个子数组进行快速排序。
• 合：对两个子数组进行合并。

2.3. 猜数字大小 leetCode 374

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(low, mid - 1)
        } else {
            return rec(mid + 1, high)
        }
    }
    return rec(1, n)
};

时间复杂度和空间复杂度都是 O(logn)

2.4. 翻转二叉树 leetCode 226

var invertTree = function(root) {
    if (!root) return null;
    return {
        val: root.val,
        left: invertTree(root.right),
        right: invertTree(root.left),
    }
};

时间复杂度和空间复杂度都是 O(n)

2.5. 相同的树 leetCode 100

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验
这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

var isSameTree = function(p, q) {

    if (!p && !q) return true;
    if (p && q && p.val === q.val && 
        isSameTree(p.left, q.left) &&
        isSameTree(p.right, q.right)
    ) {
        return true
    }
    return false
};

2.6. 对称二叉树 leetCode 101

给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

var isSymmetric = function(root) {
    if(!root) return true
    const rec = (left,right) => {
        if (!left && !right) return true;
        if (
            left && right && left.val === right.val &&
            rec(left.left, right.right) &&
            rec(left.right, right.left)
        ) {
            return true
        } else {
            return false
        }
    }
    return rec(root.left, root.right)
};