230. Kth Smallest Element in a BST

Given a binary search tree, write a functionkthSmallestto find thekth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

S: inorder traversal O(n)

    int kthSmallest(TreeNode* root, int k) {
        TreeNode* result = getNum(root, k); 
        return result->val;
    }
    TreeNode* getNum(TreeNode* root, int& k) {
        if (root == nullptr) return nullptr;
        TreeNode* left = getNum(root->left, k);
        if (left != nullptr) return left;
        k--;
        if (k == 0) return root;
        return getNum(root->right, k);
    }

270. Closest Binary Search Tree Value

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

Note:

• Given target value is a floating point.
• You are guaranteed to have only one unique value in the BST that is closest to the target.

S: BST 特性进行binary search O(logn)

不要把double转化为int比较，否则会损失精度

    int closestValue(TreeNode* root, double target) {
        int val = root->val;
        TreeNode* next = target > root->val? root->right : root->left;
        if (!next) return val;
        int nextVal = closestValue(next, target);
        return abs(val - target) < abs(nextVal -target) ? val : nextVal;
    }

272. Closest Binary Search Tree Value II

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 thanO(n) runtime (where n= total nodes)?

S: inorder traversal, stack O(n)

用inorder traversal 按顺序遍历BST。将比target小的数由小到大存入before stack，比target大的数由大到小存入after stack。

对两个stack由堆顶开始进行merge sort得到k个数

class Solution {
public:
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        vector<int> result(k);
        traverse(root, target, false);
        traverse(root, target, true);
        for (int i = 0; i < k; ++i) {
            if (before.empty()) {
                result[i] = after.top();
                after.pop();
            } else if (after.empty()) {
                result[i] = before.top();
                before.pop();
            } else {
                double gapBefore = abs((double)before.top() - target);
                double gapAfter = abs((double)after.top() - target);
                if (gapBefore > gapAfter) {
                    result[i] = after.top();
                    after.pop();
                } else {
                    result[i] = before.top();
                    before.pop();
                }
            }
        }
        return result;
    }

    void traverse(TreeNode* root, double target, bool isReverse) {
        if (!root) return;
        stack<TreeNode*> stk;
        TreeNode* node = root;
        while (!stk.empty() || node) {
            while (node) {
                stk.push(node);
                node = isReverse? node->right : node->left;
            }
            node = stk.top();
            stk.pop();
            if ((isReverse && node->val <= target) || (!isReverse && node->val > target)) return;
            if (isReverse) after.push(node->val);
            else before.push(node->val);
            node = isReverse? node->left : node->right;
        }
    }

private:
    stack<int> before, after;  
};