跃迁引擎

空気を読んだ雨降らないでよ

iOS Research & Development


二叉搜索树的第k大节点

剑指 Offer 54. 二叉搜索树的第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
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
33
34
35
36
37
38
39
40
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int kthVal = 0, count = 0;
public int kthLargest(TreeNode root, int k) {
// 递归中序遍历
// 二叉搜索树的一个特性:通过中序遍历所得到的序列,就是有序的。
traverse(root, k);
return kthVal;
}

private void traverse(TreeNode root, int k) {
// 二叉搜索树右子节点比根节点大,左子节点比根节点小
// 注意是第K大,所以右->根->左;第K小才是左->根->右

// 直接先遍历右子节点,因为右节点是最大的
if (root.right != null) {
traverse(root.right, k);
}
// 如果右子节点中没有满足k的值,那么最大值就是根节点
// 因为count从0计数,k>=1,所以当count加1后的结果等于k时,那么该根节点的值就是第k大的值。
// 注意:1.count++返回原来的值,++count返回加1后的值。
// 2.count++不能作为左值,而++count可以
if (++count == k) {
kthVal = root.val;
return;
}
// 走到这里说明递归了右节点仍未找到符合k的值,所以我们接着遍历左节点,直到找出符合k的值
if (root.left != null) {
traverse(root.left, k);
}
}
}
最近的文章

为 ReactiveCocoa 提供可独立区分延迟执行和间隔执行时间的定时器扩展

为 RAC 定时器提供一个可独立区分延迟执行和间隔执行时间的定时器扩展 …

, , , , 开始阅读
更早的文章

从上到下打印二叉树

剑指 Offer 32 - II. 从上到下打印二叉树 II …

, , 开始阅读
comments powered by Disqus