Vault 101

xjay2007's Blog

0%

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

发表于 更新于 分类于 ， Valine：

题目描述

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

示例 1:

1
2
3
4
5
6
7
输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 1

示例 2:

1
2
3
4
5
6
7
8
9
输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 3

进阶：
如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？

题解

中序遍历

思路

  • 对于二叉搜索树，使用中序遍历即可按从小到大的排序方式获取所有元素。
  • 使用栈来存储访问的元素。

时间复杂度

  • 时间复杂度为O(n)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// C++
int kthSmallest(TreeNode* root, int k) {
    stack<TreeNode*> s; // 初始化一个空栈
    auto p = root;
    // 遍历到最左端的节点
    while (p) {
        s.push(p);
        p = p->left;
    }
    // 目前栈顶为最小值
    int i = 0;
    while (!s.empty()) {
        auto top = s.top();
        s.pop();
        ++i;
        if (i == k) {
            // 当弹出k个值时停止
            return top->val;
        }
        top = top->right;
        if (top) {
            // 放入右子节点，并遍历到其最左端子节点
            while (top) {
                s.push(top);
                top = top->left;
            }
        }
    }
    return -1;
}

进阶：修改节点数据结构

思路

  • 每个节点记录一个变量，表示该节点左子树的节点数。
  • 假设根节点的左子树有 N 个节点。
    • 如果k=N+1 ，则根节点为第k小的元素。
    • 如果k<N，则需要在左子树中递归查找第k小的元素。
    • 如果k>N+1，则需要在右子树中查找第k-N-1小的元素。
  • 时间复杂度为O(h)，h 为二叉树的高度。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// C++
int kthSmallest3(TreeNode* root, int k) {
    if (!root) {
        return -1;
    }
    auto p = root;
    while (p) {
        if (p->lCount + 1 == k) {
            return p->val;
        } else if (k > p->lCount) {
            k = k - (p->lCount + 1);
            p = p->right;
        } else {
            p = p->left;
        }
    }
    return -1;
}

参考：https://www.geeksforgeeks.org/find-k-th-smallest-element-in-bst-order-statistics-in-bst/

相似文章