Array.prototype.mergeSort = function () {
  const rec = (arr) => {
    if (arr.length == 1) return arr  // 递归终止条件，直到每个组只有一个元素（保证有序）
    const mid = arr.length >> 1 //这里的作用等价于: Math.floor(arr.length/2)
    const left = arr.slice(0, mid) //1.将数组一分为二
    const right = arr.slice(mid, arr.length)
    const orderLeft = rec(left) //2.递归调用
    const orderRight = rec(right)
    const res = []
    while (orderRight.length || orderLeft.length) { //3.合并
      if (orderLeft.length && orderRight.length) {
                        // 两个数组都有值的情况下比较队头大小,小的先出队
        res.push(
          orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift()
        ) 
      } else if (orderLeft.length) {
        res.push(orderLeft.shift())
      } else {
        res.push(orderRight.shift())
      }
    }
    return res
  }
        //这里是在Array的原型上添加的mergeSort方法，this代指每个array实例，也就是数组
  const res = rec(this)
        // 对结果进行浅拷贝，赋值给this
  res.forEach((v, i) => {
    this[i] = v
  })
}

Array.prototype.quickSort = function () {
  const rec = (arr) => {
    if (arr.length <= 1) return arr //递归终止条件，数组已经是有序()
    const left = []
    const right = []
    const mid = arr[0]
    for (let i = 1; i < arr.length; i++) { //2.分 将小于基准的元素放在left，大于基准的元素放在right
      if (arr[i] < mid) { 
        left.push(arr[i]) 
      } else {
        right.push(arr[i])
      }
    }
    return [...rec(left), mid, ...rec(right)] //2.对基准左右的数组进行递归
  }
  const res = rec(this)
  res.forEach((v, i) => (this[i] = v))
}

/** 
 * 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) {}
 */
var guessNumber = function(n) {
    const rec = (low,high)=>{ // 递归函数
        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) // 答案比猜测的值大，缩小区间到【mid+1，high】
        }else {
            return rec(low,mid-1) // 答案比猜测的值小，缩小区间到【low,mid-1】
        }
    }
    return rec(1,n)
};

var invertTree = function(root) {
    const rec = (n)=>{
        if(!n) return //递归终止条件
        const temp = n.left //交换左右子树
        n.left = n.right
        n.right = temp
       if(n.left!=null){
            rec(n.left)
       }
       if(n.right!=null){
        rec(n.right)
       }
    }
    rec(root)
    return root
};

var invertTree = function(root) {
   if(!root) return null //终止递归条件
   return {
       val:root.val,
       left:invertTree(root.right),
       right:invertTree(root.left)
   }
};

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

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