题目
分析
应为二叉搜索树是“左小右大”的特性,所以对二叉搜索树进行中序遍历一定是一个升序遍历。所以用一个列表存下来二叉搜索树的顺序,列表第k-1个元素不就是第k小的元素了嘛。所以关键是得知道中序遍历可以得到一个二叉搜索树升序结果。
代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
self.return_list=[]
res=self.traverse(root)
return res[k-1]
def traverse(self,root):
if root:
self.traverse(root.left)
if root!=None:
self.return_list.append(root.val)
self.traverse(root.right)
return self.return_list
版权声明:本文为weixin_43631284原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。