230. 二叉搜索树中第 K 小的元素
一句话套路中序遍历第 k 个 / BST 迭代器
题目描述
给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 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 <= 1040 <= Node.val <= 104
进阶:如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 k 小的值,你将如何优化算法?
思路
时间
O(h + k)空间
O(h)思路
BST 中序遍历第 k 个即答案。用 Q94 的迭代模板,数到 k 直接返回,不用遍历完整棵树 —— 这是它比「中序数组化」强的地方。
延伸
若频繁调用且树会变动,应在结点里维护「子树大小」字段(Q776 思路)。
图解
二叉树(来自本仓库测试数据,
nullopt 表示空位)逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0230 {
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
stack<TreeNode*> st;
TreeNode* cur = root;
while (cur || !st.empty()) {
while (cur) {
st.push(cur);
cur = cur->left;
}
cur = st.top();
st.pop();
if (--k == 0) return cur->val; // 第 k 个被访问的结点
cur = cur->right;
}
return -1; // 题目保证 k 合法
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0230::Solution s;
TreeNode* a = buildTree({3, 1, 4, nullopt, 2});
CHECK_EQ(s.kthSmallest(a, 1), 1);
CHECK_EQ(s.kthSmallest(a, 3), 3);
freeTree(a);
TreeNode* b = buildTree({5, 3, 6, 2, 4, nullopt, nullopt, 1});
CHECK_EQ(s.kthSmallest(b, 3), 3);
freeTree(b);