LeetCode 230 Kth Smallest Element in a BST (Python)

题目

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:

You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

解题思路

一个BST的中序遍历就是将树中的所有节点排序，所有就返回中序遍历的第k个数，可以有递归和非递归两种做法

代码

# 递归

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        def inorder(root):
            if not root:
                return
            res = inorder(root.left)
            if res is not None:
                return res
            self.k -= 1
            if self.k == 0:
                return root.val
            else:
                return inorder(root.right)
            
        self.k = k
        return inorder(root)

# 非递归

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        stack = []
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if k == 0:
                return root.val
            root = root.right

视频讲解 YouTube<--欢迎点击订阅

视频讲解 bilibili<--欢迎点击订阅

Related Issues not found

Please contact @MaxMing0 to initialize the comment