C++ deque better than O(n)


  • 0
    B

    we maintain a queue of nodes, and 2 pointers to the largest value in left hand side and smallest value in right hand side

    For each iteration, we only process half of the sub tree from the two pointers, so it is like a binary search and only in worst case we would traverse the while tree.

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<int> closestKValues(TreeNode* root, double target, int k) {
            vector<int> ret;
            if(!root) return ret;
            deque<TreeNode*> ans;
            ans.push_back(root);
            TreeNode * leftSubRoot = root -> left;
            TreeNode * rightSubRoot = root -> right;
            if(leftSubRoot)
                getLeftNodes(ans, leftSubRoot->right);
            if(rightSubRoot)
                getRightNodes(ans, rightSubRoot->left);
            
            while(leftSubRoot || rightSubRoot)
            {
                if(leftSubRoot && (ans.size() < k || fabs(leftSubRoot->val - target) <= fabs(ans.back()->val - target)))
                {
                    ans.push_front(leftSubRoot);
                    leftSubRoot = leftSubRoot -> left;
                    if(leftSubRoot)
                        getLeftNodes(ans, leftSubRoot -> right);
                }
                else if(rightSubRoot && (ans.size() < k || fabs(rightSubRoot->val - target) <= fabs(ans.front()->val - target)))
                {
                    ans.push_back(rightSubRoot);
                    rightSubRoot = rightSubRoot -> right;                   
                    if(rightSubRoot)
                        getRightNodes(ans, rightSubRoot -> left);
                }
                else
                {
                    break;
                }
                clean(ans, target, k);
            }
            clean(ans, target, k);
            while(!ans.empty())
            {
                ret.push_back(ans.front()->val);
                ans.pop_front();
            }
            return ret;
        }
                   
        void getLeftNodes(deque<TreeNode*> & ans, TreeNode * root)
        {
            if(!root) return;
            getLeftNodes(ans, root->right);
            ans.push_front(root);
            getLeftNodes(ans, root->left);
        }
    
        void getRightNodes(deque<TreeNode*> & ans, TreeNode * root)
        {
            if(!root) return;
            getRightNodes(ans, root->left);
            ans.push_back(root);
            getRightNodes(ans, root->right);
        }
                   
        void clean(deque<TreeNode*> & ans, double target, int k)
        {
            while(ans.size() > k)
            {
                if(fabs(ans.front()->val - target) > fabs(ans.back()->val - target))
                {
                    ans.pop_front();                
                }
                else
                {
                    ans.pop_back();
                }
            }
        }
    };

Log in to reply
 

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