C++ iterative solution using two iterators pred and succ with two stacks


  • 1
    Y
    int get_next_pred(stack<TreeNode*>& pred){
        int res = pred.top()->val;
        TreeNode* x = pred.top()->left;
        pred.pop();
        while(x){
            pred.push(x);
            x = x->right;
        }
        return res;
    }
    
    int get_next_succ(stack<TreeNode*>& succ){
        int res = succ.top()->val;
        TreeNode* x = succ.top()->right;
        succ.pop();
        while(x){
            succ.push(x);
            x = x->left;
        }
        return res;
    }
    
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        vector<int> res;
        TreeNode* curr = root;
        stack<TreeNode*> pred;
        while(curr){
            if(curr->val == target){
                pred.push(curr);
                break;
            }
            else if(curr->val < target){
                pred.push(curr);
                if(!curr->right) break;
                curr = curr->right;
            }
            else{
                if(!curr->left) break;
                curr = curr->left;
            }
        }
        stack<TreeNode*> succ;
        curr = root;
        while(curr){
            if(curr->val == target){
                succ.push(curr);
                break;
            }
            else if(curr->val>target){
                succ.push(curr);
                if(!curr->left) break;
                curr = curr->left;
            }
            else{
                if(!curr->right) break;
                curr = curr->right;
            }
        }
        int found = 0;
        if(!succ.empty() && !pred.empty() && succ.top()->val == pred.top()->val) get_next_pred(pred);
        while(found<k){
            if(succ.empty()) res.push_back(get_next_pred(pred));
            else if(pred.empty()) res.push_back(get_next_succ(succ));
            else{
                double succ_diff = abs((double)succ.top()->val - target);
                double pred_diff = abs((double)pred.top()->val - target);
                if(succ_diff>pred_diff) res.push_back(get_next_pred(pred));
                else res.push_back(get_next_succ(succ));
            }
            found++;
        }
        return res;
    }

  • 0
    T

    Do good in finding next and last.


Log in to reply
 

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