分而治之是算法设计中的一个方法
它将一个问题分成多个和原问题的小问题，递归解决小问题

归并排序

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

快速排序

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

LeetCode（374）猜数字大小

二分搜索法

分： 计算中间元素，分割数组
解： 递归的在较大或者较小子数组进行二分搜索

leetCode() 翻转二叉树

leetCode(100) 相同的二叉树

两棵树相同： 根节点是否相同，左子树是否相同，右子树是否相同
分： 获取左子树，右子树
解： 递归的判断两个树的左子树，右子树，是否相同
时间复杂度: O(n)。 是递归，遍历了树的所有节点
空间复杂度: O(n)

  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.     if(!p && !q) return true;
  16.     const rec = (a, b) => {
  17.         if(!a && !b) return true
  18.         if(a && b && a.val === b.val && rec(a.left, b.left) && rec(a.right, b.right)) {
  19.             return true
  20.         }
  21.         return false
  22.     }
  23.     return rec(p, q)
  24. };

leetCode(101) 对称二叉树

转化为： 转换为左右子树是否镜像
分: 树1的左子树和树二的右子树
解：递归的判断树1的左子树和树2的右子树是否镜像
时间复杂度: O(n)。 是递归，遍历了树的所有节点
空间复杂度: O(n)

  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.     if(!root) return true
  15.     const isMirror = (l, r)=>{
  16.         if(!l && !r) return true
  17.         if(l && r && l.val === r.val &&
  18.             isMirror(l.left, r.right) &&
  19.             isMirror(l.right, r.left)
  20.         ) {
  21.             return true
  22.         }
  23.         return false
  24.     }
  25.     return isMirror(root.left, root.right)
  26. };