bst中最接近t的k个数

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

  • Given target value is a floating point.
  • You may assume k is always valid, that is: k ≤ total nodes.
  • You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

Hint:

  1. Consider implement these two helper functions:
    　　i. getPredecessor(N), which returns the next smaller node to N.
    　　ii. getSuccessor(N), which returns the next larger node to N.
  2. Try to assume that each node has a parent pointer, it makes the problem much easier.
  3. Without parent pointer we just need to keep track of the path from the root to the current node using a stack.
  4. You would need two stacks to track the path in finding predecessor and successor node separately.

用中序遍历和k长队列，O(n)解法

vector<int> closestKValues(TreeNode* root, double target, int k) {
    deque<int> q;
    inorder(root, target, k, q);
    return vector<int>(q.begin(), q.end());
}

void inorder(TreeNode *root, double target, int k, deque<int> &q) {
    if (!root) return;
    // 用中序遍历和k长队列
    inorder(root->left, target, k, q);
    if (q.size() < k) {
        q.push_back(root->val);
    } else if (abs(root->val - target) < abs(q.front() - target)) {
        q.pop_front();
        q.push_back(root->val);
    } else return;
    inorder(root->right, target, k, q);
}

找前驱和后继，O(klgn)解法

vector<int> closestKValues(TreeNode* root, double target, int k) {
    // 前驱栈pred和后继栈succ
    stack<TreeNode *> pred, succ;
    auto p = root;
    while (p) {
        if (target < p->val) {
            succ.push(p);
            p = p->left;
        } else {
            pred.push(p);
            p = p->right;
        }
    }
    
    vector<int> ans;
    while (k--) {
        // 往两端的两指针
        if (succ.empty() || (!pred.empty() && target - pred.top()->val < succ.top()->val - target)) { // 选前驱
            ans.push_back(pred.top()->val);
            getPredecessor(pred);
        } else {
            ans.push_back(succ.top()->val);
            getSuccessor(succ);
        }
    }
    return ans;
}

// 类似i--，到左子树最右儿子的路径
void getPredecessor(stack<TreeNode *> &pred) {
    auto node = pred.top(); pred.pop();
    auto p = node->left;
    while (p) {
        pred.push(p);
        p = p->right;
    }
}

// 类似j++，到右子树最左儿子的路径
void getSuccessor(stack<TreeNode *> &succ) {
    auto node = succ.top(); succ.pop();
    auto p = node->right;
    while (p) {
        succ.push(p);
        p = p->left;
    }
}