Clean c++ O(k + logn) solution


  • 0
    1. binary search to the bottom while building stack for prev and succ
    2. merge sort like mechanism to push k values.
    public:
        vector<int> closestKValues(TreeNode* root, double target, int k) {
            stack<TreeNode *> predecessor;
            stack<TreeNode *> successor;
            TreeNode *node;
            while (root) {
                node = root;
                if (root->val < target) {
                    predecessor.push(root);
                    root = root->right;
                } else {
                    successor.push(root);
                    root = root->left;
                }
            }
            vector<int> result;
            TreeNode *prev = getPredecessor(predecessor), *next = getSuccessor(successor);
            while (k--) {
                if (next == NULL || (prev != NULL && target - prev->val < next->val - target)) {
                    result.push_back(prev->val);
                    prev = getPredecessor(predecessor);
                } else {
                    result.push_back(next->val);
                    next = getSuccessor(successor);
                }
            }
            return result;
        }
    private:
        TreeNode *getPredecessor(stack<TreeNode *> &predecessor) {
            if (predecessor.size() == 0)
                return NULL;
            TreeNode *prev = predecessor.top();
            predecessor.pop();
            TreeNode *left = prev->left;
            while (left) {
                predecessor.push(left);
                left = left->right;
            }
            return prev;
        }
        
        TreeNode *getSuccessor(stack<TreeNode *> &successor) {
            if (successor.size() == 0)
                return NULL;
            TreeNode *next = successor.top();
            successor.pop();
            TreeNode *right = next->right;
            while (right) {
                successor.push(right);
                right = right->left;
            }
            return next;
        }
    

Log in to reply
 

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