题目描述：给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
代码实现
中序实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
private List<TreeNode> nodes = new ArrayList<>();
public int kthSmallest(TreeNode root, int k) {
inorders(root);
return nodes.get(k).val;
}
public void inorders(TreeNode root){
if (root == null){
return;
}
inorders(root.left);
nodes.add(root);
inorders(root.right);
}
}
|
递归优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
private int idx = 0;
private int idxVal = 0;
public int kthSmallest(TreeNode root, int k) {
inorders(root, k);
return idxVal;
}
public void inorders(TreeNode root, int k) {
if (root == null) {
return;
}
inorders(root.left, k);
idx++;
if (idx == k) {
idxVal = root.val;
}
inorders(root.right, k);
}
}
|