傳送門

題目要求

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

思路

深度遍歷BST左子樹，使用變量記錄節(jié)點個數(shù)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def __init__(self):
        self.count = 0
        self.res = None
    
    def kthSmallest(self, root, k):
        if not root.left and not root.right:
            self.count += 1
            if self.count == k:
                self.res = root.val
            return
        if root.left:
            self.kthSmallest(root.left, k)
        self.count += 1
        if self.count == k:
            self.res = root.val
            return
        if root.right:
            self.kthSmallest(root.right, k)