給定一個二叉搜索樹，編寫一個函數?kthSmallest?來查找其中第?k?個最小的元素。
說明：
你可以假設 k 總是有效的，1 ≤ k ≤ 二叉搜索樹元素個數。示例 1:
輸入: root = [3,1,4,null,2], k = 1
? ?3
? / \
?1 ? 4
? \
?? 2
輸出: 1
示例 2:輸入: root = [5,3,6,2,4,null,null,1], k = 3
? ? ? ?5
? ? ? / \
? ? ?3 ? 6
? ? / \
? ?2 ? 4
? /
?1
輸出: 3
進階：
如果二叉搜索樹經常被修改（插入/刪除操作）并且你需要頻繁地查找第 k 小的值，你將如何優化?kthSmallest?函數？
解法一：
class Solution
{
public:int kthSmallest(TreeNode* root, int k) {vector<int> num;help(root, num); return num[k-1];}void help(TreeNode *root, vector<int> &num){if(!root) return;help(root->left, num);num.push_back(root->val);help(root->right, num);}
};解法二:
class Solution
{
public:int kthSmallest(TreeNode* root, int k) {int num = -1;help(root, k); }void help(TreeNode *root, int &k, int &num){if(!root) return;help(root->left, k, num);if(0 == --k){num = root->val;return;}help(root->right, k, num);}
};
?
)
)
)