[演算法題目] Find the closest value in Binary Search Tree

本題資訊

難度：easy
使用語言：C++
相關概念：Binary Search Trees

題目敘述

Given a binary search tree and a target integer value. The task is to find the node with a minimum absolute difference with the given target value.

這題要求在二元樹中找出最接近目標值的元素。以下面為例子，假設目標值是 12，則會回傳 13。

Idea

由二元樹的特性，從樹或任何子樹的 root 切兩半，一半的元素比 root 小、另外一半的元素都比 root 大，可以利用這個特性，決定走的方向。

首先當然是先比較 |目標值 – 目前最接近的數| 和 |目標值 – 目前走訪的元素| 哪一個較小，並且更新目前最接近的數字。再來是決定走向，如果目標值小於目前走訪的元素，那我們會往左邊走，因為往左走遇到的數一定比目前走訪的元素還小，丟去同一邊才有更接近目標值的可能（不可能右手邊元素存在較接近的元素），反之亦然。以上步驟重複到走到底為止。

class BST {
public:
  int value;
  BST *left;
  BST *right;

  BST(int val);
  BST &insert(int val);
};

int findClosestValueInBst(BST *tree, int target) {
  int result = tree->value;
  while (tree != NULL){
    if (abs(target - result) > abs(target - tree->value))
      result = tree->value;
    if (target < tree->value){
      tree = tree->left;
    } else {
      tree = tree->right;
    }
  }
  return result;
}