Leetcode 230. Kth Smallest Element in a BST

Description: Given the root of a binary search tree, and an integer k, return the kth (1-indexed) smallest element in the tree.

Link: 230. Kth Smallest Element in a BST

Examples:

Example 1:

Input: root = [3,1,4,null,2], k = 1
Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

思路: 二叉搜索树的中序遍历是有序数组，从小到达排列，要找到第k小的数，就只需要在中序遍历的过程中，每次遍历一个节点，k = k-1,然后k == 0时的节点值就是第k小的值。

class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        self.k = k
        self.res = root.val
        self.dfs(root)
        return self.res
    
    def dfs(self, root):
        if not root:
            return 
        self.dfs(root.left)
        self.k -= 1
        if self.k == 0:
            self.res = root.val
        self.dfs(root.right)

日期: 2021-04-12 今天终于刷题破百了