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

    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)) {
            } else {
        return res;
    void inorder(TreeNode *root, vector<double> &total) {
        if (!root) return;
        inorder(root->left, total);
        inorder(root->right, total);

Log in to reply

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