272. Closest Binary Search Tree Value II - cocoder39/coco39_LC GitHub Wiki

272. Closest Binary Search Tree Value II

  • Inorder traversal bst with using stack. [link to preorder traversal]
  • Maintain a dq of size k.

T = O(n), S = O(n) where n is the number of nodes in bst.

vector<int> closestKValues(TreeNode* root, double target, int k) {
        deque<int> dq;
        stack<TreeNode*> s;
        
        while (root || ! s.empty()) {
            if (root) {
                s.push(root);
                root = root->left;
            }
            else {
                TreeNode* node = s.top();
                s.pop();
                if (dq.size() < k)
                    dq.push_back(node->val);
                else {
                    if (abs(node->val - target) < abs(dq.front() - target)) {
                        dq.pop_front();
                        dq.push_back(node->val);
                    }
                    else
                        break;
                }
                root = node->right;
            }
        }
        
        vector<int> res;
        while (! dq.empty()) {
            res.push_back(dq.front());
            dq.pop_front();
        }
        return res;
    }

time complexity is O(log n + k) and space complexity is O(log n) for balanced bst

use find a value in bst method to initialize two stacks. during the finding process, closest one would be on the top of stack.

taking pred for example, after popping it out, we need refill the pred stack. Since the top of stack is always the closest pred, go right would not be pred, can only go left. then go all the way right to push closer pred into stack.

class Solution {
public:
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        vector<int> res;
        stack<TreeNode*> succ;
        stack<TreeNode*> pred;
        
        initStack(pred, succ, root, target);
        while (k-- > 0) {
            if (succ.empty()) { 
                res.push_back(nextPred(pred));
            } 
            else if (pred.empty()) {
                res.push_back(nextSucc(succ));
            } 
            else {
                double succ_diff = abs((double)succ.top()->val - target);
                double pred_diff = abs((double)pred.top()->val - target);
                succ_diff < pred_diff ? res.push_back(nextSucc(succ)) : res.push_back(nextPred(pred));
            }
        }
        return res;
    }

    void initStack(stack<TreeNode*>& pred, stack<TreeNode*>& succ, TreeNode* root, double target) { //O(log n)
        while (root) {
            if (root->val <= target) { //closest pred on the top
                pred.push(root);
                root = root->right;
            }
            else{ //closest succ on the top
                succ.push(root);
                root = root->left;
            }
        }
    }
    
    int nextSucc(stack<TreeNode*>& succ) {
        TreeNode* cur = succ.top();
        succ.pop();
        int res = cur->val;
        cur = cur->right;
        while (cur) {
            succ.push(cur);
            cur = cur->left;
        }
        return res;
    }

    int nextPred(stack<TreeNode*>& pred) {
        TreeNode* cur = pred.top();
        pred.pop();
        int res = cur->val; //currently closest pred
        cur = cur->left; //thus only going left can guarantee pred
        while (cur) { //closest pred on the top
            pred.push(cur);
            cur = cur->right;
        }
        return res;
    }
};
⚠️ **GitHub.com Fallback** ⚠️