Straight forward Inorder Traversal Based O(n) Solution in C++ (20ms)


  • 0
    J
    class Solution {
    public:
        vector<int> closestKValues(TreeNode* root, double target, int k) {
            if(root==NULL || k<=0) return {};
            
            vector<int> window;
            int size=0;
            stack<TreeNode*> s;
            TreeNode* p = root;
            while(p || !s.empty()){
                while(p){
                    s.push(p);
                    p=p->left;
                }
                p=s.top();
                s.pop();
                
                if(size<k){
                    window.push_back(p->val);
                    size++;
                }
                else{
                    if(target<=(double) window[0]) return window;
                    if(abs(target-window[0])> abs(target-p->val)){
                        window.erase(window.begin());
                        window.push_back(p->val);
                    }
                    else
                        break;
                }
                
                p=p->right;
            }
            return window;
        }
    };

Log in to reply
 

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