10.算法设计思想之"分而治之"

image.png image.png image.png image.png

// 0 mid
// 1 higher than the guess number
//-1 lower than the guess number
//var guess = function(num) {}
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);
}

时间复杂度 O(logN) && 空间复杂度 O(n)

LeeCode：226.翻转二叉树

image.png image.png image.png

// function TreeNode(val) {
//   this.val = val;
//   this.left = this.right = null;
// }

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

时间复杂度 O(n) - 树的节点数量 && 空间复杂度 O(h) - 递归，堆栈（树的高度）

image.png image.png image.png

// function TreeNode(val) {
//   this.val = val;
//   this.left = this.right = null;
// }

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

时间复杂度 O(n) -树的节点数 && 空间复杂度 O(n) O(logN)

LeetCode：101. 对称二叉树

image.png image.png image.png

// function TreeNode(val) {
//   this.val = val;
//   this.left = this.right = null;
// }

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

  }
  return isMirror(root.left, root.right);
};

时间复杂度 O(n) -树的节点数 && 空间复杂度 最坏O(n) 最好O(logN)