Standard vector solutions c++


  • 0
    K
    class Solution {
    

    public:

    void helper(TreeNode * root, double target, vector<TreeNode*>&pre, vector<TreeNode*>&suc)
    {
        if(!root)return;
        helper(root->left, target, pre, suc);
        if(root->val < target)pre.push_back(root);
        else suc.insert(suc.begin(),root);
        helper(root->right, target, pre, suc);
    }
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        double p=INT_MAX, s=INT_MAX;
        vector<int>res;
        vector<TreeNode*>pre;
        vector<TreeNode*>suc;
        helper(root, target, pre, suc);
    
        while(k>0 && !pre.empty() && !suc.empty())
        {
          p=abs(pre.back()->val-target);
          s=abs(suc.back()->val-target);
           if(p <= s ){
               res.push_back(pre.back()->val);
               pre.pop_back();
           }
           if(s<p){
            res.push_back(suc.back()->val);
            suc.pop_back();
           }
            k--;
        }
        while(k>0)
        {
            if(!pre.empty()){
                res.push_back(pre.back()->val);
                pre.pop_back();
            }
            if(!suc.empty())
            {
                res.push_back(suc.back()->val);
                suc.pop_back();
            }
            k--;
        }
    
        return res;
    }
    };
    //pre[1,3,4,6]
    //suc[14,10,9,8,7]
    //tree: [8,3,10,1,6,9,14,#,#,4,7]

Log in to reply
 

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