leetcode.png
题目
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 1
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
**输出: **3
进阶：
如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？
数据结构定义
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
分析
这是一道中等难度的题，题解的关键词是二叉搜索树，二叉搜索树相信大家都知道它的特征是，左子树的任意结点值<根结点值<右子树结点值。
要查找它的第K小的元素值，应该怎么做呢？提到二叉树，离不开遍历问题，根据二叉搜索树的特征，它的中序遍历正好能得到一个有序列表。
如果递归地进行中序遍历，将弹出来的结果保存都列表中，那么得到的列表将是一个从小到大的有序列表，取第 k-1 个即可满足要求。
实现
在最初的Python实现中，我采用了递归遍历整个搜索二叉树后直接返回第k-1个值的做法。
Python 实现 第一版
class Solution:
def kthSmallest(self, root: TreeNode, k: int) -> int:
rs = []
self.midVisit(root, rs)
return rs[k-1]
def midVisit(self, root: TreeNode, rs: list):
if not root:
return
self.midVisit(root.left, rs)
rs.append(root.val)
self.midVisit(root.right, rs)
结果
结果比较一般。
再思考多一步，既然二叉搜索树中序遍历是逆序的，那么直接遍历到第k个就可以停止遍历了。
Python 实现 第二版
class Solution:
def kthSmallest(self, root: TreeNode, k: int) -> int:
rs = []
self.midVisit(root, rs, k)
return rs[k-1]
def midVisit(self, root: TreeNode, rs: list, k: int):
if not root:
return
self.midVisit(root.left, rs, k)
if len(rs)<k:
rs.append(root.val)
else:
return
self.midVisit(root.right, rs, k)
结果
速度的提升是比较明显的。
微信公众号: 程序员的碎碎念
