題目
給定一個二叉搜索樹，編寫一個函數 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 函數
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
思路
- 二叉搜索樹BST有一個重要性質：中序遍歷為排序數組，根據這個性質，我們可將問題轉化為尋找中序遍歷第k個節點的值；
-
實現的方法是建立兩個全局變量res和count，分別用于存儲答案與計數：
在每次訪問節點時，計數器-1；
當count == 0時，代表已經到達第k個節點，此時記錄答案至res； - 找到答案后，已經不用繼續遍歷，因此每次判斷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
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
