import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
PriorityQueue<Integer> queue; // 优先队列,存储节点值(最大堆)
HashSet<Integer> set; // 哈希集合,用于判断节点值是否已存在
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param k int整型
* @return int整型
*/
public int kthLargest (TreeNode root, int k) {
// write code here
queue = new PriorityQueue<>
(Collections.reverseOrder()); // 初始化优先队列为最大堆
set = new HashSet<>();
dfs(root); // 深度优先搜索遍历二叉树
k = k - 1;
while (k > 0) { // 弹出队列中前k-1个元素
queue.poll();
k--;
}
return queue.peek(); // 返回队列中的顶部元素,即第k大的节点值
}
private void dfs(TreeNode root) {
if (root == null) {
return;
}
if (!set.contains(
root.val)) { // 如果哈希集合中不存在该节点值,则将其加入优先队列和哈希集合
queue.offer(root.val);
set.add(root.val);
}
dfs(root.left); // 递归遍历左子树
dfs(root.right); // 递归遍历右子树
}
}
代码使用的是Java编程语言
该题考察的知识点是二叉树的遍历和优先队列的使用。
代码的解释如下:
- 定义了一个名为
TreeNode的类,表示二叉树的节点,包含一个整数值val和指向左右子节点的指针。 - 定义了一个名为
Solution的类,其中包含了两个成员变量:一个优先队列(最大堆)queue,用于存储节点值;一个哈希集合set,用于判断节点值是否已存在。 kthLargest方法是求解第k大节点值的方法。首先初始化优先队列为最大堆,并创建一个空的哈希集合。然后通过调用dfs方法深度优先搜索遍历二叉树,将节点值加入优先队列和哈希集合中。接下来,将k减1,因为优先队列中的元素是按照降序排列的。然后循环弹出队列中的元素,弹出的次数为k,这样队列的顶部元素即为第k大的节点值。最后返回队列的顶部元素。dfs方法是一个递归方法,用于深度优先搜索遍历二叉树。如果当前节点为空,直接返回。如果哈希集合中不存在该节点值,则将其加入优先队列和哈希集合。然后递归调用dfs方法遍历左子树和右子树。- 注意,代码中使用了Java集合类
PriorityQueue(优先队列)和HashSet(哈希集合)来实现功能。
总结:该Java代码实现了求解二叉树中第k大节点值的功能,通过深度优先搜索将节点值加入优先队列和哈希集合中,然后通过弹出操作获取第k大的节点值。这样可以确保优先队列中始终存储着前k大的节点值。

京公网安备 11010502036488号