【Leetcode算法题】230. 二叉搜索树中第K小的元素

By Long Luo

230. 二叉搜索树中第K小的元素题目如下:

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

给定一个二叉搜索树的根节点root,和一个整数kk,请你设计一个算法查找其中第kk个最小元素(从11开始计数)。

示例 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 <= 10^4
0 <= Node.val <= 10^4

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

方法一:中序遍历 + 递归

思路与算法:

二叉搜索树具有如下性质:

  • 结点的左子树只包含小于当前结点的数。
  • 结点的右子树只包含大于当前结点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

二叉树的中序遍历即按照访问左子树——根结点——右子树的方式遍历二叉树;在访问其左子树和右子树时,我们也按照同样的方式遍历;直到遍历完整棵树。

因为二叉搜索树和中序遍历的性质,所以二叉搜索树的中序遍历是按照键增加的顺序进行的。于是,我们可以通过中序遍历找到第kk个最小元素。

代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int kthSmallest(TreeNode root, int k) {
List<Integer> nums = new ArrayList<>();
inOrder(root, nums);
return nums.get(k - 1);
}

public void inOrder(TreeNode root, List<Integer> numberList) {
if (root == null) {
return;
}

inOrder(root.left, numberList);
numberList.add(root.val);
inOrder(root.right, numberList);
}

复杂度分析:

  • 时间复杂度:O(N)O(N),其中NN是树的节点数。
  • 空间复杂度:O(N)O(N),需要额外存储每个节点的值。

方法二:中序遍历 + 迭代

思路与算法:

方法一使用的是递归来进行中序遍历,实际上,我们也可以使用迭代方法来进行中序遍历,如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> nums = new ArrayList<>();
while (root != null || !stack.empty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
nums.add(root.val);
root = root.right;
}

return nums.get(k - 1);
}

实际上,使用迭代方法,我们可以在找到答案后就停止,而不需要遍历整棵树,优化后的代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.empty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
k--;
if (k == 0) {
break;
}
root = root.right;
}

return root.val;
}

复杂度分析:

  • 时间复杂度:O(H+k)O(H+k),其中HH是树的高度。在开始遍历之前,我们需要O(H)O(H)到达叶结点。当树是平衡树时,时间复杂度取得最小值O(logN+k)O(\log N + k);当树是线性树(树中每个结点都只有一个子结点或没有子结点)时,时间复杂度取得最大值O(N+k)O(N+k)

  • 空间复杂度:O(H)O(H),栈中最多需要存储HH个元素。当树是平衡树时,空间复杂度取得最小值O(logN)O(\log N);当树是线性树时,空间复杂度取得最大值O(N)O(N)