您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# LeetCode怎么找出二叉搜索树中第K小的元素
## 问题描述
在LeetCode中，[230. 二叉搜索树中第K小的元素](https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/)题目要求：
给定一个二叉搜索树（BST）的根节点和一个整数k，找出其中第k个最小的元素（从1开始计数）。
示例：
输入：root = [3,1,4,null,2], k = 1 输出：1
## 二叉搜索树特性回顾
二叉搜索树（BST）具有以下关键性质：
1. **左子树**所有节点的值 < **根节点**的值
2. **右子树**所有节点的值 > **根节点**的值
3. 左右子树也必须是二叉搜索树
这个性质决定了**中序遍历BST会得到升序排列的序列**，这是解决本题的核心突破口。
## 方法一：递归中序遍历
### 算法步骤
1. 执行中序遍历（左-根-右）
2. 记录遍历到的节点值
3. 当访问到第k个元素时立即返回
### 代码实现
```python
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
self.res = None
self.count = 0
def inorder(node):
if not node or self.res is not None:
return
inorder(node.left)
self.count += 1
if self.count == k:
self.res = node.val
return
inorder(node.right)
inorder(root)
return self.res
相比递归方法： - 避免递归栈溢出风险 - 可以在找到第k个元素后立即终止遍历
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
stack = []
curr = root
count = 0
while stack or curr:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
count += 1
if count == k:
return curr.val
curr = curr.right
适用于需要多次查询的场景，通过预处理优化后续查询。
class TreeNodeWithCount:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
self.left_count = 0
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
# 首先构建带计数的树结构
new_root = self.build_count_tree(root)
return self.query(new_root, k)
def build_count_tree(self, node):
if not node:
return None
new_node = TreeNodeWithCount(node.val)
new_node.left = self.build_count_tree(node.left)
new_node.right = self.build_count_tree(node.right)
new_node.left_count = self.count_nodes(new_node.left)
return new_node
def count_nodes(self, node):
if not node:
return 0
return 1 + self.count_nodes(node.left) + self.count_nodes(node.right)
def query(self, node, k):
if node.left_count + 1 == k:
return node.val
elif node.left_count >= k:
return self.query(node.left, k)
else:
return self.query(node.right, k - node.left_count - 1)
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 递归中序 | O(H + k) | O(H) | 单次查询 |
| 迭代中序 | O(H + k) | O(H) | 单次查询（推荐） |
| 记录节点数 | 预处理O(N)，查询O(H) | O(N) | 多次查询 |
在实际编码中需要注意： 1. 空树情况（题目保证k有效） 2. k超出树节点总数（题目保证1 ≤ k ≤ N） 3. 树退化为链表的情况
解决BST第k小元素问题的核心在于利用BST的中序有序特性。对于： - 面试场景：推荐迭代中序遍历法，代码简洁且效率高 - 频繁查询场景：可考虑预处理节点数的优化方法 - 大规模数据：可能需要考虑非递归实现避免栈溢出
掌握这个问题的解法不仅有助于理解BST的特性，也为处理其他树相关问题提供了重要思路框架。 “`
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。