給定一個(gè)二叉搜索樹，編寫一個(gè)函數(shù)?kthSmallest?來(lái)查找其中第?k?個(gè)最小的元素。

說(shuō)明：
你可以假設(shè) k 總是有效的，1 ≤ k ≤ 二叉搜索樹元素個(gè)數(shù)。

示例 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
進(jìn)階：
如果二叉搜索樹經(jīng)常被修改（插入/刪除操作）并且你需要頻繁地查找第 k 小的值，你將如何優(yōu)化?kthSmallest?函數(shù)？

解法一：

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);} };

?

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的【Leetcode | 49】230. 二叉搜索树中第K小的元素的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。