Day 30 ：BST中找最接近的值＆感谢文

简单叙述一下题目：题目会给你一棵BST以及一个数。我们要从这个BST中找出最接近这个数的节点值。

以下图为例

假设题目要我们找出这棵树中和12最接近的值，用看的可以知道答案为13。

直觉的想法就是我从根开始，把每个值去和target比较（取相差的绝对值），额外用一个变数(closest)去存现在和target最接近的值找出最接近的。

那麽一开始我们应该要把closest设成无限大，我们从root(10)开始，比较
｜infinity - 12(target)｜= infinity
｜10 - 12｜ = 2

因为 infinity 远大於2 ，所以我们可以把 closest从infinity换成10。

我们理所当然可以使用拜访每个数的节点一个个的确认，但既然题目给我们的树是BST，我们当然不能忽略这个特性！我们知道现在10左手边的所有数都一定会比10还要小，而目前要找最靠近12的值，且12又来的比10还大，所以我们根本不需要去查10左手边以下的数对吧？

所以我们移到了15
｜10 - 12｜= 2
｜15 - 12 ｜= 3

所以10目前胜利，closet不变。

那思考一下：我们先在该往15的左边还是右边找？
想一想！！
是左边对吧？因为15现在输了，我们要找更小的才能更接近12！
接着我们就会发现13，最後会结束在因为13没有左儿子於是13就是整解。

那我们在想一个问题，我们什麽时候不用继续找下去？
因为是要找最接近的数，所以当我们遇到绝对值算出来恰为0的时候，应该就可以停止了吧？

平均来看：时间复杂度会是O(logN)，N是数的节点数

但最糟的的时候还是有可能来到O(N)，当BST只有一个斜斜的树枝(branch)，完全没占到BST的优势。

而空间复杂度会根据我们的程序码有所不同，如果以递回方式(call stack)，最糟会来到O(N)。如果用迭代的方式，则空间复杂度会是O(1)。

最後就是程序码拉！递回＆迭代两种都写写看～

function findClosestValueInBst(tree, target) {
  return findCloset(tree, target, tree.value);
}

function findCloset(tree, target, closest) {
  if (tree === null) return closest;
  if (Math.abs(target - closest) > Math.abs(target - tree.value)) {
    closest = tree.value;
  }
// recursive
  if (target < tree.value) {
    return findCloset(tree.left, target, closest);
  } else if (target > tree.value) {
    return findCloset(tree.right, target, closest);
  } else {
    return closest;
  }
}

class BST {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function findClosestValueInBst(tree, target) {
  return findCloset(tree, target, tree.value);
}
// iterate
function findCloset(tree, target, closest) {
  let current = tree;
  while (current !== null) {
    if (Math.abs(target - closest) > Math.abs(target - current.value)) {
      closest = current.value;
    }
    if (target < current.value) {
      current = current.left;
    } else if (target > current.value) {
      current = current.right;
    } else {
      break;
    }
  }
  return closest;
}

class BST {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

终於撑完最後一天了！
必须得说如果不是两位好队友，ycchiuuuu & pjchender 的互相鼓励，我大概第10多天就想偷懒弃赛了，他们对我来说都是很好的学习榜样，经验也比我丰富超多，很推荐大家阅读React 前端工程师的两把刷子＆ Javascript 从写对到写好！