Very easy to understand C++ code , O(nlogn) time


  • 0
    V
    Very simple idea:  
    
    1. make a inorder traversal (or whatever traversal you like), and record the (node value, distance to target) as pair during traversal
    2. Sort the traversal vector using user-defined sorting function.
    3. Take the first k pairs from the traversal vector , the 'int' part goes to the final result.
    void inorderTraversal(TreeNode* root, vector<pair<int,double>>& result,double target)
    {
        if(root==NULL) return ;
        inorderTraversal(root->left, result,target);
        result.push_back(make_pair(root->val,abs(root->val-target)));
        inorderTraversal(root->right,result,target);
    }
    
    static bool myCompare(pair<int,double>& p1, pair<int,double>& p2)
    {
        return p1.second<p2.second;
    }
    
    vector<int> closestKValues(TreeNode* root, double target, int k) {
         vector<pair<int,double>> nodes;
         inorderTraversal(root,nodes,target);
         sort(nodes.begin(),nodes.end(),myCompare);
         vector<int> result;
         for(int i=0;i<k;i++)
         {
             result.push_back(nodes[i].first);
         }
         return result;
    }

Log in to reply
 

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