1 题目

给定一棵二叉搜索树,请找出其中第k大的节点。
示例 1:

输入: root = [3,1,4,null,2], k = 1
    3
  /   \
1     4
  \
    2
输出: 4
示例2:

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

限制:

1 ≤ k ≤ 二叉搜索树元素个数

作者:画手大鹏
链接:https://leetcode-cn.com/leetbook/read/illustrate-lcof/xspy85/
来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

2 中序遍历

该方法为先使用一个集合类容器放置该树的中序遍历的结果序列,因为二叉搜索树的中序遍历是一个升序的序列,那么第$k$大的数则为第$list.size()-k$个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int kthLargest(TreeNode root, int k) {
List<Integer> res = new ArrayList<>();
inOrder(root, res);
return res.get(res.size() - k);
}

private void inOrder(TreeNode root, List<Integer> res) {
if (root == null)
return;
inOrder(root.left, res);
res.add(root.val);
inOrder(root.right, res);
}
}

这种算法的时间复杂度和空间复杂度都是$O(n)$,其中$n$是二叉搜索树的节点个数,那么这种方法并没有利用二叉搜索树的性质。

3 改进版

我们知道二叉搜索树的左子树的所有值都小于根节点的值,右子树的所有值都大于根节点的值。且中序遍历的序列是一个升序的序列,那么中序遍历的顺序是left->root->right。这种遍历方式决定了中序遍历的结果是一个升序的序列,题目中要求返回第$k$大的数,那么就是中序遍历序列从后往后算起第$k$个数。
我们可以不用遍历完这棵树,只需要遍历$k$次即可,我们修改树的遍历次序,改为right->root-left。那么遍历的最终的结果就是一个降序的序列。我们定义一个全局的索引,判断当前遍历到了第几个节点,当遍历到第$k$个节点时,我们就可以结束遍历返回结果。

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int index = 0, res = 0;
public int kthLargest(TreeNode root, int k) {
this.index = k;
dfs(root);
return res;
}

private void dfs(TreeNode root) {
if (root == null) return;

dfs(root.right);
index--;
if (index == 0) {
res = root.val;
return;
}
dfs(root.left);
}
}

写在最后

欢迎大家关注鄙人的公众号【麦田里的守望者zhg】,让我们一起成长,谢谢。
微信公众号