題目： LeetCode - 230. Kth Smallest Element in a BST

題目說明

給一個 Binary Search Tree 及一個整數 k，求 Tree 中第 k 小的值。

解題思路

使用遞迴將值推入 v，由於是 BST，所以先將左子樹推入，再推入自己的值，最後推入右子樹，這樣 v 裡面就是由小到大排序了，最後回傳 v[k - 1] 即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution {
public:
    void putsIn(TreeNode* root)
    {
        if(!root)
            return;
        putsIn(root->left);
        v.push_back(root->val);
        putsIn(root->right);
    }
    int kthSmallest(TreeNode* root, int k) {
        putsIn(root);
        return v[k - 1];
    }
private:
    vector<int> v;
};