导航
导航
文章目录
  1. 题目
  2. 翻译

LeetCode-230.Kth Smallest Element in a BST

题目

Given a binary search tree, write a function kthSmallest to find the k th smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Hint:
1、Try to utilize the property of a BST.
2、What if you could modify the BST node’s structure?
3、The optimal runtime complexity is O(height of BST).

翻译

给出一颗二叉搜索树,编写函数 kthSmallest ,查找其中第k小的树。
注意:
你可以认为k总是合法的,1 ≤ k ≤ 二叉搜索树的总元素数。
跟进:
如果二叉搜索树的修改(插入/删除操作)很频繁,而你需要经常查找第k个元素呢?你将如何改进算法?
提示:
1、尝试利用二叉搜索树的性质。
2、如果你可以修改二叉搜索树的结构呢?
3、理想的运行时间复杂度是O(二叉搜索树的高度)。

利用二叉搜索树的性质:中序遍历二叉搜索树,可以得到一个递增的数组:

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = root;
int index = 0;
while (true) {
while (node != null) {
stack.push(node);
node = node.left;
}
node = stack.pop();
if (++index == k) return node.val;
node = node.right;
}
}
}

跟进:
修改二叉搜索树的结构,对于每个节点,增加其左子树的节点个数属性 leftNums,每次做树修改时更新。
当查找第k小的元素时,只要用k与leftNums属性比较。
如果 k < leftNums,则在其左子树中查找;如果k == leftNums,则返回根节点值;如果 k > leftNums,则在其右子树中查找:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* int leftNums;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int kthSmallest(TreeNode root, int k) {
TreeNode node = root;
while (true) {
if (k == node.leftNums + 1) return node.val;
else if (k < node.leftNums + 1) node = node.left;
else {
k -= node.leftNums + 1;
node = node.right;
}
}
}
}

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