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

  • Post author:
  • Post category:其他



题目


分析

应为二叉搜索树是“左小右大”的特性,所以对二叉搜索树进行中序遍历一定是一个升序遍历。所以用一个列表存下来二叉搜索树的顺序,列表第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 版权协议,转载请附上原文出处链接和本声明。