HHot 100C++ 图解

230. 二叉搜索树中第 K 小的元素

中等 二叉树 3 帧动画 在力扣上做

一句话套路中序遍历第 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 <= 104
  • 0 <= Node.val <= 104

 

进阶:如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 k 小的值,你将如何优化算法?

思路

时间O(h + k)
空间O(h)

思路

BST 中序遍历第 k 个即答案。用 Q94 的迭代模板,数到 k 直接返回,不用遍历完整棵树 —— 这是它比「中序数组化」强的地方。

延伸

若频繁调用且树会变动,应在结点里维护「子树大小」字段(Q776 思路)。

图解

1 2 3 4 5 6
二叉树(来自本仓库测试数据,nullopt 表示空位)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/08_binary_tree.cpp20 行
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 合法
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q230_kth_smallest8 行
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);

↑↓ 选择↵ 打开/ 随时唤起