C++ solution O(n) time and O(n) space,I did not figure out how to do it in O(LogN), Asking for help


  • 0
    M

    I did not figure out how to do it in O(LogN), Any hints or suggestions or solutions are welcome.

    vector<int> closestKValues(TreeNode* root, double target, int k) {
        vector<int> res;
        if (!root) return res;
        vector<double> total;
        inorder(root, total);
        auto ta = lower_bound(total.begin(), total.end(), target);
        if (ta == total.end()) copy(total.end() - k, total.end(), back_inserter(res));
        auto left = ta - 1, right = ta;
        while (res.size() < k && (left >= total.begin() || right < total.end())) {
            int val_l = INT_MAX, val_r = INT_MAX;
            if (left >= total.begin()) val_l = *left;
            if (right < total.end()) val_r = *right;
            if (abs(val_l - target) < abs(val_r - target)) {
                res.push_back(val_l);
                left--;
            } else {
                res.push_back(val_r);
                right++;
            }
        }
        return res;
    }
    void inorder(TreeNode *root, vector<double> &total) {
        if (!root) return;
        inorder(root->left, total);
        total.push_back(root->val);
        inorder(root->right, total);
    }

Log in to reply
 

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