-Find Closest value in BST

tags: Easy

Due to the properties of BST，故解都是 O(log(n)) time

解法一：用遞歸，遞歸用了call stack，故O(n) space

using namespace std;

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

  BST(int val);
  BST &insert(int val);
};
int findClosestValueInBst(BST *tree, int target);
int findClosestValueInBstHelper(BST *tree, int target, int closest);

// O(log(n)) time O(n) space
// O(n) space due to Using recursive (call stack)
int findClosestValueInBst(BST *tree, int target) {
  return findClosestValueInBstHelper(tree, target, tree->value);
}
int findClosestValueInBstHelper(BST *tree, int target, int closest){
    if (abs(target-closest) > abs(target-tree->value))
        closest = tree->value;
    if (target > tree->value &&  tree-> right != nullptr)
        return findClosestValueInBstHelper(tree->right, target, closest);
    else if (target < tree->value &&  tree-> left != nullptr)
        return findClosestValueInBstHelper(tree->left, target, closest);
    else
        return closest;
}

解法二：用迴圈，O(1) space

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

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

int findClosestValueInBst(BST *tree, int target);
int findClosestValueInBstHelper(BST *tree, int target, int closest);

int findClosestValueInBst(BST *tree, int target) {
  return findClosestValueInBstHelper(tree, target, tree->value);
}

int findClosestValueInBstHelper(BST *tree, int target, int closest){
    BST *curNode = tree;
    while (curNode){
        if (abs(target-closest) > abs(target - curNode->value))
            closest = curNode->value;
        if (target > curNode->value)
            curNode = curNode->right;
        else if (target < curNode->value)
            curNode = curNode->left;
        else
            break;
    }
    return (int)closest;
}