题解 | #二叉树之寻找第k大# java

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编程语言

该题考察的知识点是二叉树的遍历和优先队列的使用。

代码的解释如下：

1. 定义了一个名为TreeNode的类，表示二叉树的节点，包含一个整数值val和指向左右子节点的指针。
2. 定义了一个名为Solution的类，其中包含了两个成员变量：一个优先队列（最大堆）queue，用于存储节点值；一个哈希集合set，用于判断节点值是否已存在。
3. kthLargest方法是求解第k大节点值的方法。首先初始化优先队列为最大堆，并创建一个空的哈希集合。然后通过调用dfs方法深度优先搜索遍历二叉树，将节点值加入优先队列和哈希集合中。接下来，将k减1，因为优先队列中的元素是按照降序排列的。然后循环弹出队列中的元素，弹出的次数为k，这样队列的顶部元素即为第k大的节点值。最后返回队列的顶部元素。
4. dfs方法是一个递归方法，用于深度优先搜索遍历二叉树。如果当前节点为空，直接返回。如果哈希集合中不存在该节点值，则将其加入优先队列和哈希集合。然后递归调用dfs方法遍历左子树和右子树。
5. 注意，代码中使用了Java集合类PriorityQueue（优先队列）和HashSet（哈希集合）来实现功能。

总结：该Java代码实现了求解二叉树中第k大节点值的功能，通过深度优先搜索将节点值加入优先队列和哈希集合中，然后通过弹出操作获取第k大的节点值。这样可以确保优先队列中始终存储着前k大的节点值。