算法（二）分而治之

1. 介绍

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

场景一：归并排序

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

场景二：快速排序

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

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

226. 翻转二叉树

解题思路：

• 先翻转左右子树，再将子树换个位置
• 符合“分、解、合”特性
• 考虑选择分而治之

解题步骤：

• 分：获取左右子树
• 解：递归地翻转左右子树
• 合：将翻转后的左右子树换个位置放到根节点上

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

100. 相同的树

解题思路：

• 两个树：根节点的值相同，左子树相同，右子树相同
• 符合“分、解、合”特性
• 考虑选择分而治之

解题步骤：

• 分：获取两个树的左子树和右子树
• 解：递归地判断两个树的左子树是否相同，右子树是否相同
• 合：将上述结果合并，如果根节点的值也相同，则树相同

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
};

101. 对称二叉树

解题思路：

• 转化为：左右子树是否镜像
• 分解为：树1的左子树和树2的右子树是否镜像，树1的右子树和树2的左子树是否镜像
• 符合“分、解、合”特性，考虑选择分而治之

解题步骤：

• 分：获取两个树的左子树和右子树
• 解：递归地判断树1和树2的右子树是否镜像，树1的右子树和树2的左子树是否镜像
• 合：如果上述都成了，且根节点值也相同，两个树就镜像

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