C++ inorder traversal with deque to maintain result Time O(N) space O(K)


  • 5
    M

    The idea is to have a in-order traversal to visit and use deque to maintain current result.
    Therefore, the time complexity is O(N) and the space complexity is O(K) for deque.
    Please note for the following code I use stack to do the traversal so there's additional space O(logN) for stack. However, we can use Morris Traversal to replace the stack with O(1) additional pointers.

    class Solution {
    public:
        // brute force solution 
        // space complexity deque: O(K) ; stack: O(logN) stack; for stack part, we can remove it by morris traversal  
        // time complexity O(N)
        vector<int> closestKValues(TreeNode* root, double target, int k) {
            if (root == NULL || k <= 0) { return vector<int>(); }
            deque<int> myQ; 
            stack<TreeNode *> ss; // use stack to do in-order search 
            while (root || !ss.empty()) {
                while(root) {
                    ss.push(root);
                    root = root->left;
                } 
                root = ss.top();
                ss.pop();
                // let's process root now
                if (myQ.size() < k) {
                    myQ.push_back(root->val);
                } else { // size == k, 
                    // if root->val is too small, update queue; otherwise, compare with queue's front
                    if (target > root->val || (abs(target - root->val) < abs(target - myQ.front()))) {
                        myQ.push_back(root->val);
                        myQ.pop_front();
                    } else {  
                        break; 
                    }
                }
                // move to next one 
                root = root->right;
            }
            return vector<int>(myQ.begin(), myQ.end());
        }
    };

Log in to reply
 

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