簡單敘述一下題目：題目會給你一棵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 從寫對到寫好！

此外，
感謝每一位訂閱我以及曾經閱讀且熱心修正過我文章或是分享心得的讀者，謝謝你們！

鐵人賽下台一鞠躬。

結束，是另一個開始。