C++ two stack 25 line, simple clean


  • 0
    X
    1. keep track of parent in big/small stack
    2. compare the value from 2 stacks, if small is chosen, pop it out and push back all right node of its left node, similar for big.
    class Solution {
    public:
        vector<int> closestKValues(TreeNode* root, double target, int k) {
            TreeNode* c = root, *n, *bt, *st;
            stack<TreeNode*> big, small;
            while (c) 
                if (c->val >= target) { big.push(c); c=c->left; }
                else { small.push(c); c=c->right; }
        
            vector<int> r;
            while (k > 0) {
                if (!big.empty())  bt = big.top();
                if (!small.empty()) st = small.top(); 
                
                if (big.empty() || (!small.empty() && abs(bt->val - target) > abs(st->val - target))) {
                    r.push_back(st->val);
                    c = st->left; small.pop();
                    while (c) { small.push(c); c= c->right; }
                } else {
                    r.push_back(bt->val);
                    big.pop();
                    c = bt->right;
                    while (c) { big.push(c); c=c->left; }
                }
                k--;
            }
            return r;
        }
    };```

Log in to reply
 

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