本文主要是介绍[LeetCode] 230. Kth Smallest Element in a BST,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目内容
https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/
给定一个二叉搜索树,编写一个函数 kthSmallest
来查找其中第 k 个最小的元素。
说明:
你可以假设 k 总是有效的,1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:输入: root = [3,1,4,null,2], k = 13/ \1 4\2
输出: 1
示例 2:输入: root = [5,3,6,2,4,null,null,1], k = 35/ \3 6/ \2 4/1
输出: 3
题目思路
记住,二叉搜索树可以通过中序遍历的方式来得到一个完整的升序排列。所以我们进行中序遍历就行。但是与此同时,我们不需要把整个树都遍历了,那纯粹是个铁憨憨。只要设置一个指示符,当符合要求时跳出就可以。
程序代码
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution(object):def __init__(self):self.result=[]self.End=Falsedef kthSmallest(self, root, k):""":type root: TreeNode:type k: int:rtype: int"""if not root:returnif self.End==False:self.kthSmallest(root.left,k)if self.End==False:self.result.append(root.val)if len(self.result)==k:print(self.result)self.End=Trueif self.End==False:self.kthSmallest(root.right,k)return self.result[-1]
这篇关于[LeetCode] 230. Kth Smallest Element in a BST的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!