当前位置：首页 > news >正文

LeetCode 热题 100 230. 二叉搜索树中第 K 小的元素

news 2025/5/16 14:07:53

LeetCode 热题 100 | 230. 二叉搜索树中第 K 小的元素

大家好，今天我们来解决一道经典的二叉搜索树问题——二叉搜索树中第 K 小的元素。这道题在 LeetCode 上被标记为中等难度，要求查找二叉搜索树中的第 K 小的元素。

问题描述

给定一个二叉搜索树的根节点 root，和一个整数 k，请你设计一个算法查找其中第 K 小的元素（从 1 开始计数）。

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

提示：

树中的节点数为 n。
1 <= k <= n <= 10^4
0 <= Node.val <= 10^4

解题思路

方法一：中序遍历（递归）

初步分析：
- 二叉搜索树（BST）的中序遍历可以得到一个有序的节点值序列。
- 因此，使用中序遍历可以找到二叉搜索树中的第 K 小的元素。
步骤：
- 递归进行中序遍历，遍历到第 K 个元素时返回其值。
代码实现：

class Solution:def kthSmallest(self, root: TreeNode, k: int) -> int:self.count = 0self.result = 0def travel(t):if t is None:returntravel(t.left)  # 左self.count += 1  # 中if self.count == k:self.result = t.valtravel(t.right)  # 右travel(root)return self.result

方法二：中序遍历（迭代）

初步分析：
- 如果不想使用递归，可以使用显式栈来模拟中序遍历。
- 遍历到第 K 个元素时返回其值。
步骤：
- 使用栈模拟中序遍历，通过栈记录每次访问的节点。
代码实现：

class Solution:def kthSmallest(self, root: TreeNode, k: int) -> int:stack = []current = rootwhile current or stack:while current:stack.append(current)current = current.leftcurrent = stack.pop()k -= 1if k == 0:return current.valcurrent = current.right

方法三：基于分治的优化

初步分析：
- 通过计算每个节点的左子树节点数，可以在 O(log n) 的时间复杂度内找到第 K 小的元素。
- 如果 K 小于左子树的节点数，则在左子树中查找；如果 K 等于左子树的节点数 + 1，则当前节点即为第 K 小的元素；否则在右子树中查找。
步骤：
- 计算每个节点的左子树节点数，根据 K 的值决定在左子树还是右子树查找。
代码实现：

class Solution:def kthSmallest(self, root: TreeNode, k: int) -> int:def countNodes(node):if not node:return 0return 1 + countNodes(node.left) + countNodes(node.right)left_count = countNodes(root.left)if k <= left_count:return self.kthSmallest(root.left, k)elif k > left_count + 1:return self.kthSmallest(root.right, k - left_count - 1)else:return root.val

复杂度分析

时间复杂度：
- 中序遍历（递归和迭代）：O(n)，其中 n 是二叉搜索树的节点数。需要遍历整个树。
- 基于分治的优化方法：O(log n) 到 O(n)，最坏情况下需要遍历整个树，但在平衡树中可以在 O(log n) 内完成查找。
空间复杂度：
- 中序遍历（递归）：O(n)，用于递归调用栈。
- 中序遍历（迭代）：O(n)，用于存储栈的额外空间。
- 基于分治的优化方法：O(h)，其中 h 是树的高度，递归调用栈的深度等于树的高度。

进阶问题

如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 K 小的值，可以考虑以下优化方法：

使用自平衡的二叉搜索树：
- 使用 AVL 树或红黑树，可以保证树的高度最小化，从而使得查找、插入和删除操作的时间复杂度为 O(log n)。
维护子树大小信息：
- 在每个节点上维护两个额外的信息：左子树中的节点数（称为“左序”）和右子树中的节点数（称为“右序”）。每次插入或删除操作后，更新这些统计信息。利用节点的左序和右序信息，可以在不完全遍历树的情况下找到第 K 小的节点。