230. 二叉搜索树中第K小的元素

https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/

解法一：中序遍历

利用二叉搜索树的性质，中序遍历得到增序序列，然后增加一个全局计数，数到第k个就记录

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        self.count = 0    #全局计数
        self.res = -sys.maxsize    #记录第k个
        self.inorder(root, k)
        return self.res
    
    def inorder(self, root, k):
        if not root:
            return
        self.inorder(root.left, k)
        self.count += 1    #计数+1
        if self.count == k:    #到达第k个结点
            self.res = root.val
        self.inorder(root.right, k)

改进：可以先将所有结点值存在列表中，然后直接取第k个元素

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        self.data = []    #结点值列表
        self.inorder(root)
        return self.data[k-1]
    
    def inorder(self, root):
        if not root:
            return
        self.inorder(root.left)
        self.data.append(root.val)
        self.inorder(root.right)