LeetCode230(二叉搜索树中第k小的元素)

题目:

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

思路:

  题目中二叉树为二叉搜索树,很容易想到将数中序遍历,得到的顺序即为排序顺序,从而很容易就得到第k小的元素。而实现中序遍历
有递归和循环两种写法。

代码:

1.递归:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private int count = 0;
private int res = 0;
// 递归
public int kthSmallest(TreeNode root, int k) {
count = k;
inTraverse(root);
return res;
}
public void inTraverse(TreeNode root) {
if (root != null) {
inTraverse(root.left);
count--;
if (count == 0) {
res = root.val;
}
inTraverse(root.right);
}
}

2.排序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 public int kthSmallest1(TreeNode root, int k) {
Deque<TreeNode> stack = new LinkedList<>();
int count = 0;
TreeNode node = root;
while(node != null || !stack.isEmpty()) {
while(node != null) {
stack.push(node);
node = node.left;
}
if (!stack.isEmpty()) {
node = stack.pop();
count++;
if (count == k) {
return node.val;
}
node = node.right;
}
}
throw new RuntimeException("参数错误");
}

复杂度分析及总结:

1.递归:

  时间复杂度:
    O(n)。
  空间复杂度:
    O(n)。

2.循环:

  时间复杂度:
    O(n)。
  空间复杂度:
    O(n)。

总结:

  注意递归写法中需要利用全局变量记录第k小的值。