Share my O(logN+K) time , DFS and binary search in C++


  • -2
    S

    We maintain two arrays to track the larger and smaller number.
    class Solution {

    public:
        //binary search, in order traversal, two arrays
        //smaller array stores nearest numbers<target in descending order
        //larger array stores nearest numbers>=target in ascending order
        //O(logN+k);
        void DFS(TreeNode *node, double target, int k, 
        vector<int> &larger, vector<int> &smaller){
            if(!node)return;
            if(target<=node->val){
                DFS(node->left,target,k,larger,smaller);
                larger.push_back(node->val);
                if(larger.size()>=k)return; //Skip beacuse we only need nearest k numbers
                DFS(node->right,target,k,larger,smaller);
            }
            else{
                DFS(node->right,target,k,larger,smaller);
                smaller.push_back(node->val);
                if(smaller.size()>=k)return;//Skip beacuse we only need nearest k numbers
                DFS(node->left,target,k,larger,smaller);
            }
        }
        vector<int> closestKValues(TreeNode* root, double target, int k) {
            vector<int> larger, smaller, ans;
            DFS(root,target,k,larger,smaller);
            int i=0,j=0;
            //merge smaller array and larger array, get the nearest k numbers
            while(ans.size()<k){
                if(i==larger.size())ans.push_back(smaller[j++]);
                else if(j==smaller.size())ans.push_back(larger[i++]);
                else{
                    if(larger[i]-target<=target-smaller[j])ans.push_back(larger[i++]);
                    else ans.push_back(smaller[j++]);
                }
            }
            return ans;
        }
    };

  • 0
    Y

    I suspect your solution is not a O(K) solution. Since you are pushing nodes->val into array, and then merge together. Do you access all nodes in the tree? if so, your solution is O(n).

    For a O(K) solution you must push TreeNode* into stack. that's the only way you can avoid visiting all nodes.


Log in to reply
 

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