题目
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
