題目
給定一個二叉搜索樹，編寫一個函數(shù) kthSmallest 來查找其中第 k 個最小的元素。
說明：
你可以假設(shè) k 總是有效的，1 ≤ k ≤ 二叉搜索樹元素個數(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īng)常被修改（插入/刪除操作）并且你需要頻繁地查找第 k 小的值，你將如何優(yōu)化 kthSmallest 函數(shù)
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。
思路
- 二叉搜索樹BST有一個重要性質(zhì)：中序遍歷為排序數(shù)組，根據(jù)這個性質(zhì)，我們可將問題轉(zhuǎn)化為尋找中序遍歷第k個節(jié)點的值；
-
實現(xiàn)的方法是建立兩個全局變量res和count，分別用于存儲答案與計數(shù)：
在每次訪問節(jié)點時，計數(shù)器-1；
當(dāng)count == 0時，代表已經(jīng)到達第k個節(jié)點，此時記錄答案至res； - 找到答案后，已經(jīng)不用繼續(xù)遍歷，因此每次判斷res是否為空，若不為空直接返回。
代碼
ref：https://leetcode-cn.com/problems/two-sum/solution/kth-smallest-element-in-a-bst-ti-qian-zhong-zhi-zh/
class
Solution
:
def
kthSmallest
(
self
,
root
:
TreeNode
,
k
:
int
)
-
>
int
:
self
.
res
,
self
.
count
=
None
,
k
def
inorder
(
root
)
:
if
not
root
:
return
inorder
(
root
.
left
)
if
self
.
res
:
return
self
.
count
-=
1
if
not
self
.
count
:
self
.
res
=
root
.
val
inorder
(
root
.
right
)
inorder
(
root
)
return
self
.
res
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
