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

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

    场景

    1.归并排序

  • 分：把数组从中间一分为二

  • 解：递归地对两个子数组进行归并排序

  • 合：合并有序子数组

    2.快速排序

  • 分：选基准，按照基准把数组分成两个子数组

  • 解：递归地对两个子数组进行快速排序
  • 合：对两个子数组进行合并

    题目

    1.猜数字大小 - 374

    ```javascript /**
    • Forward declaration of guess API.
    • @param {number} num your guess
    • @return -1 if num is lower than the guess number
    • 1 if num is higher than the guess number
    • otherwise return 0
    • var guess = function(num) {} */

/**

  • @param {number} n
  • @return {number} */ var guessNumber = function(n) { // 定义递归函数 const rec = (low, high) => {
    1.    // 递归终止条件，当最小值大于最大值
    2.  if(low > high) { return }
    3.    // 取中间的值
    4.  const mid = Math.floor((low + high) /2)
    5.  // 拿到猜的结果
    6.  const res = guess(mid)
    7.  if(res === 0) {
    8.      return mid
    9.  } else if( res === -1){
    10.        // 如果猜的值比mid小
    11.        // 就继续递归搜索，并把范围缩小一半
    12.      return rec(low, mid -1)
    13.  } else {
    14.        // 如果猜的值比mid大
    15.      return rec(mid + 1,high)
    16.  }
    } // 返回递归结果 return rec(1, n) }; ```

    2.翻转二叉树

    翻转一棵二叉树。

示例：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9

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

思路：

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

解题步骤：

  • 分：获取左右子树
  • 解：递归地的翻转左右子树
  • 合：将翻转后的左右子树换个位置放到根节点上
  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @return {TreeNode}
  12.  */
  13. var invertTree = function(root) {
  14.       // 递归结束条件
  15.     if(!root) return null
  16.       // 递归地翻转树的左右节点
  17.     return {
  18.         val: root.val,
  19.         left: invertTree(root.right),
  20.         right: invertTree(root.left)
  22.     }
  24. };

3.相同的树 - 100

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

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

示例 1：
image.png
输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：
image.png
输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：
image.png
输入：p = [1,2,1], q = [1,1,2]
输出：false

提示：

  • 两棵树上的节点数目都在范围 [0, 100] 内
  • -104 <= Node.val <= 104

思路：

  • 两个树：根节点的值相同，左子树相同，右子树相同
  • 符合“分、解、合”的思路

解题步骤：

  • 分：获取两个树的左子树合右子树
  • 解：递归判断两个树的左子树是否相同、右子树是否相同
  • 合：将上述结果合并，如果根节点的值也相同，树就相同
  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} p
  11.  * @param {TreeNode} q
  12.  * @return {boolean}
  13.  */
  14. var isSameTree = function(p, q) {
  15.       // 排除特殊的空树，返回true
  16.     if (!p && !q) return true
  17.     // 判断根节点的值
  18.     if(p && q && p.val === q.val &&
  19.            // 判断左右节点是否相同
  20.         isSameTree(p.left, q.left) &&
  21.         isSameTree(p.right, q.right)
  22.     ) {
  23.         return true
  24.     }
  26.     return false
  28. };
  • 时间复杂度：O(N - 树的节点数)
  • 空间复杂度：最坏：O(N - 树的节点数) 最好：O(logN) 均匀分布

4.对称二叉树 - 101

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

  1. 1<br />   / \<br />  2   2<br /> / \ / \<br />3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

  1. 1<br />   / \<br />  2   2<br />   \   \<br />   3    3<br /> <br />进阶：<br />你可以运用递归和迭代两种方法解决这个问题吗？

思路：

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

解题步骤：

  • 分：获取两个树的左子树和右子树
  • 解：递归的判断树1的左子树是否和树2的右子树是否是镜像的，树1的右子树是否和树2的左子树是否是镜像的
  • 合：如果上述成立，且根节点值相同，则树为镜像的树
  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @return {boolean}
  12.  */
  13. var isSymmetric = function(root) {
  14.       // 处理特殊用例
  15.     if(!root) return true
  16.     const isMirror = (l, r) => {
  17.         //  递归终点
  18.         if(!l && !r) return true
  19.           // 判断根节点是否相同
  20.         if(l && r && l.val === r.val &&
  21.                // 递归地判断左子树和右子树是否镜像
  22.             isMirror(l.left, r.right) &&
  23.             isMirror(l.right, r.left)
  24.         ) {
  25.               // 是镜像
  26.             return true
  27.         }
  28.           // 否则返回false
  29.            return false
  30.     }
  31.         // 返回
  32.     return isMirror(root.left, root.right)
  34. };
  • 时间复杂度：O(N) 递归的遍历所有节点

  • 空间复杂度：O(N) 递归会调用堆栈来存储 N为树的高度，最坏只有一侧为O(N)，最好为完全二叉树为O(logN)

    应用场景

  • 归并排序

  • 快速搜索
  • 二分搜索
  • 翻转二叉树