Closest Binary Search Tree Value I, II

Question I

one closest value

Solution

can be solved by recursion [here])(http://www.cnblogs.com/jcliBlogger/p/4763200.html)

class Solution {
public:
    int closestValue(TreeNode* root, double target) {
        if (!root) return INT_MAX;
        if (!root->left && !root->right) return root->val;

        int left = closestValue(target->left, target);
        int right = closestValue(target->right, target);

        double td = abs(root->val - target), ld = abs(left - target), rd = abs(right - target);
        if (td < ld) return (td < rd) ? root->val : right;
        else return (ld < rd) ? left : right;
    }
}

or

// recursive
int closestValue(TreeNode* root, double target) {
    int a = root->val;
    auto kid = target < a ? root->left : root->right;
    if (!kid) return a;
    int b = closestValue(kid, target);
    return abs(a - target) < abs(b - target) ? a : b;
}
// iterative
int closestValue(TreeNode* root, double target) {
    int closest = root->val;
    while (root) {
        if (abs(closest - target) >= abs(root->val - target))
            closest = root->val;
        root = target < root->val ? root->left : root->right;
    }
    return closest;
}

more solution here

Question II

k closest values

Solution

here

Solution {
public:
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        priority_queue<pair<double, int>> pq;
        closestK(root, pq, target, k);
        vector<int> closest;
        while(!pq.empty()) {
            closest.push_back(pq.top().second);
            pq.pop();
        }
        return closest;
    }
private:
    void closestK(TreeNode* node, priority_queue<pair<double, int>>pq, double target, int k){
        if(!node) return ;
        pq.push(make_pair(abs(target - node->val), node->val));
        if (pq.size() > k) pq.pop();
        closestK(node->left, pq, target, k);
        closestK(node->right, pq, target, k);
    }
}