C++_Stack_19ms_AC


  • 0

    Use two stacks as two part of the in-order sequence of BST.

    class Solution {
    stack<TreeNode*> pre1;
    stack<TreeNode*> pre2;
    public:
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        vector<int> res;
        TreeNode* Right = nullptr;
        TreeNode* Left = nullptr;
        while(true){
            while(root){
                pre1.push(root);
                root = root->left;
            }
            if(pre1.empty()) {break;}
            root = pre1.top();
            if(root->val * 1.0 >= target) {break;}
            pre1.pop();
            pre2.push(root);
            root = root->right;
        }
    
        //now we have two nodes: Left, Right 
        Left = getPredecessor();
        Right = getSuccessor();
        while(res.size() < k){
            if(Left == nullptr && Right == nullptr) break;
            if(Right == nullptr || (Right != nullptr && Left != nullptr && target - Left->val * 1.0 < Right->val * 1.0 - target)){
                res.push_back(Left->val);
                Left = getPredecessor();
            }else{
                res.push_back(Right->val);
                Right = getSuccessor();
            }
        }
        return res;
    }
    
    TreeNode* getPredecessor(){
        if(!pre2.empty()){
            TreeNode* pre = pre2.top();
            pre2.pop();
            return pre;
        }
        return nullptr;
    }
    
    TreeNode* getSuccessor(){
        if(pre1.empty()){return nullptr;}
        TreeNode* suc = pre1.top();
        pre1.pop();
        TreeNode* tmp = suc->right;
        while(tmp){
            pre1.push(tmp);
            tmp = tmp->left;
        }
        return suc;
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.