「力扣」第 230 题：二叉搜索树中第 K 小的元素
- 中文网址：230. 二叉搜索树中第K小的元素 ；
- 英文网址：230. Kth Smallest Element in a BST ，
给定一个二叉搜索树，编写一个函数
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函数？
方法一：先得到中序遍历的结果，然后找到第 k 大元素
我们利用了二分搜索树的有序性，二分搜索树的中序遍历得到的是一个有序数组，直接得到结论。
Java 代码：
import java.util.ArrayList;
import java.util.List;
public class Solution {
public int kthSmallest(TreeNode root, int k) {
List<Integer> res = new ArrayList<>();
dfs(root, res);
return res.get(k - 1);
}
private void dfs(TreeNode node, List<Integer> res) {
if (node == null) {
return;
}
dfs(node.left, res);
res.add(node.val);
dfs(node.right, res);
}
}复杂度分析
- 时间复杂度：$O(N)$，遍历了整个树。
- 空间复杂度：$O(N)$，用了一个数组存储中序序列。
方法二：在递归的时候不记录全部结果，只记录计数器
Java 代码：
public class Solution {
public int kthSmallest(TreeNode root, int k) {
count = k;
dfs(root);
return res;
}
private int count = 0;
private int res = 0;
private void dfs(TreeNode node) {
// 先写递归终止条件
if (node == null) {
// 什么都不做
return;
}
dfs(node.left);
count--;
if (count == 0) {
this.res = node.val;
}
dfs(node.right);
}
}分析：因为二分搜索树具有顺序性，所以我们可以用类似快速排序的 partition 操作来完成
1、二分搜索树的有序性；2、二叉树中序遍历，特别地，
简而言之就是在中序遍历的时候数个数，第 1 个遍历到的是第 1 个最小的元素，第 2 个遍历到的是第 2 个最小的元素，数到第 k 个够数了，就不用再遍历了。
Python 代码：
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 230. 二叉搜索树中第K小的元素
# 给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
class Solution:
# 使用中序遍历得到 BST 第 k 小的那个元素
def __init__(self):
self.k = None
self.res = None
def __dfs(self, node):
if node is None:
return
self.__dfs(node.left)
self.k -= 1
if self.k == 0:
self.res = node.val
return
self.__dfs(node.right)
def kthSmallest(self, root, k):
self.k = k
self.__dfs(root)
return self.res
等价写法：
Python 代码：
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def __init__(self):
self.counter = 0
self.res = 0
def kthSmallest(self, root, k):
# 使用递归的方法，中序遍历
if root.left:
# 不是空，才继续遍历
self.kthSmallest(root.left, k)
self.counter += 1
# print(root.val)
if self.counter == k:
# 注意：千万不能在这里返回，后序遍历还要继续进行下去
self.res = root.val
return
if root.right:
self.kthSmallest(root.right, k)
return self.resPython 代码：推荐写法
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 这种写法比 3 更好一些，在入栈的时候，就判断结点是不是空，非空才入栈
class Solution:
def kthSmallest(self, root, k):
stack = [(1, root)]
while stack:
command, node = stack.pop()
if command == 0:
k -= 1
if k == 0:
return node.val
else:
# 模拟系统栈实现中序遍历(先左边、再自己、再右边)
if node.right:
stack.append((1, node.right))
stack.append((0, node))
if node.left:
stack.append((1, node.left))Python 代码：
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def kthSmallest(self, root, k):
stack = [(1, root)]
while stack:
command, node = stack.pop()
if command == 0:
k -= 1
if k == 0:
return node.val
else:
# 模拟系统栈实现中序遍历(先左边、再自己、再右边)
if node.right:
stack.append((1, node.right))
stack.append((0, node))
if node.left:
stack.append((1, node.left))
