二叉搜索树的第k大节点


题目描述

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

示例 1:

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

示例 2:

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

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

题解

二叉搜索树的中序遍历是递增序列,那么倒序就是递减序列。

中序遍历为“左、根、右”的顺序
中序遍历的倒序为“右、根、左”的顺序

1
2
3
4
5
6
7
// 打印中序遍历
void dfs(TreeNode root) {
if(root == null) return;
dfs(root.left); // 左
System.out.println(root.val); // 根
dfs(root.right); // 右
}

所以我们只要求出二叉搜索树的中序遍历倒序的第k个节点即可。

递归解析:

  • 递归的终止条件:当节点为空的时候,越过了叶子节点,则直接返回;
  • 递归右子树:dfs(root.right);
  • 递归操作:先进行k - 1,然后判断 k 是否等于0,是则找到第k大的节点,将节点的值返回。
  • 递归左子树:dfs(root.left);

中序遍历图解

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
30
31
32
int k;
int res;
public int kthLargest(TreeNode root, int k) {
this.k = k;
dfs(root);
return res;
}

public void dfs(TreeNode t) {
if (t == null) {
return;
}
dfs(t.right);
if (k == 0) {
return;
}
if (--k == 0) {
res = t.val;
return;
}
dfs(t.left);
}

public class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode(int x) {
val = x;
}
}

复杂度分析

  • 时间复杂度 Ο(N) : 当树退化为链表时(全部为右子节点),无论 k 的值大小,递归深度都为 N ,占用 Ο(N) 时间。
  • 空间复杂度 Ο(N) : 当树退化为链表时(全部为右子节点),系统使用 Ο(N) 大小的栈空间。

来源

二叉搜索树的第k大节点 | 力扣(LeetCode)
二叉搜索树的第k大节点 | 题解(LeetCode)


文章标题:二叉搜索树的第k大节点
文章作者:cylong
文章链接:http://www.cylong.com/blog/2020/07/15/kda-jie-dian-lcof/
有问题或者建议欢迎在下方评论。欢迎转载、引用,但希望标明出处,感激不尽(●’◡’●)