分而治之 | note

# 分而治之

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

# 应用场景

# 归并排序

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

# 快速排序

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

# 算法题：猜数字大小

猜数字游戏的规则如下：


每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

-1：我选出的数字比你猜的数字小 pick < num
1：我选出的数字比你猜的数字大 pick > num
0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num

链接：https://leetcode-cn.com/problems/guess-number-higher-or-lower

解题思路：二分搜索，同样具备 “分、解、合” 的特性，考虑选择分而治之；
解题步骤：分：计算中间元素，分割数组。解：递归地在较大或者较小子数组进行二分搜索。合：不需要此步，因为在子数组中搜到就返回结果。

时间复杂度为 O(logn); 空间复杂度：O(logn);

/**
 * @param {number} n
 * @return {number}
 */
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);
};

# 算法题：翻转二叉树

翻转一棵二叉树。示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

链接：https://leetcode-cn.com/problems/invert-binary-tree

解题思路：先反转左右子树，再将子树换个位置；符合 “分、解、合” 特性；考虑选择分而治之；
解题步骤：分：获取左右子树；解：递归地翻转左右子树。合：将翻转后的左右子树换个位置放到根节点上。

时间复杂度为 O(n); 空间复杂度：O(n);

/**
 * @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)
    }
};

# 算法题：相同的树

给定两个二叉树，编写一个函数来检验它们是否相同。

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

示例 1:


输入:      1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

输出: true

链接：https://leetcode-cn.com/problems/same-tree

解题思路：两个树相同，那么根节点的值相同，左右子树相同；符合 “分、解、合” 特性；考虑选择分而治之；
解题步骤：分：获取两个数的左子树和右子树。解：递归地判断两个树的左、右子树是否相同；合：将上面的结果合并，如果根节点的值也相同，树就相同；

时间复杂度为 O(n); 空间复杂度：O(n); 递归，内部形成了一个堆栈；

/**
 * @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(p.left, q.left) &&
      isSameTree(p.right, q.right)
    ) {
        return true;
    }
    return false
};

# 算法题：对称二叉树

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

链接：https://leetcode-cn.com/problems/symmetric-tree

解题思路：转换为左右子树是否为镜像。分解为，树1的左子树和树2的右子树是否镜像，树1的右子树和树2的左子树是否镜像；符合 “分、解、合” 特性；考虑选择分而治之；
解题步骤：分：获取两个树的左子树和右子树。解：递归地判断树1的左子树和树2的右子树是否镜像，树1的右子树和树2的左子树是否镜像；合：如果上述都成立，且根节点值也相同，两个树就镜像。