【Leetcode 2583】二叉树中的第K大层和 —— 优先队列 + BFS

简介: 解题思路:- 使用队列保存节点,按层序依次保存该层节点- 使用优先队列保存每层节点值的总和,最后剔除前k个大数即可得到

2583. 二叉树中的第K大层和

给你一棵二叉树的根节点root和一个正整数k

树中的 层和 是指 同一层 上节点值的总和。

返回树中第k大的层和(不一定不同)。如果树少于k层,则返回-1

注意,如果两个节点与根节点的距离相同,则认为它们在同一层。

示例 1:

输入:root = [5,8,9,2,1,3,7,4,6], k = 2
输出:13
解释:树中每一层的层和分别是:

  • Level 1: 5
  • Level 2: 8 + 9 = 17
  • Level 3: 2 + 1 + 3 + 7 = 13
  • Level 4: 4 + 6 = 10
    第 2 大的层和等于 13 。

示例 2:

输入:root = [1,2,null,3], k = 1
输出:3
解释:最大的层和是 3 。

题目分析

解题思路:

  • 使用队列保存节点,按层序依次保存该层节点
  • 使用优先队列保存每层节点值的总和,最后剔除前k个大数即可得到

广度优先搜索(BFS)是一种图搜索算法,用于在图或树数据结构中进行遍历。BFS的基本思想是从起始节点开始,逐层地向外扩展搜索,直到达到目标节点或遍历完整个图

class Solution {
   
   
    public long kthLargestLevelSum(TreeNode root, int k) {
   
   
        PriorityQueue<Long> queue = new PriorityQueue<>(new Comparator<Long>() {
   
   
            @Override
            public int compare(Long o1, Long o2) {
   
   
                return o2.compareTo(o1);
            }
        });

        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);
        while(!nodeQueue.isEmpty()){
   
   
            int size = nodeQueue.size();
            long total = 0;
            for(int i = 0; i < size; i++){
   
   
                TreeNode tmp = nodeQueue.poll();
                total += tmp.val;
                if(tmp.left != null){
   
   
                    nodeQueue.add(tmp.left);
                }
                if(tmp.right != null){
   
   
                    nodeQueue.add(tmp.right);
                }
            }
            queue.add(total);
        }

        if(queue.size() < k){
   
   
            return -1;
        } else {
   
   
            // 剔除前k个大数
            while(--k > 0){
   
   
                queue.poll();
            }
            return queue.poll();
        }
    }
}
相关文章
|
2月前
力扣226:翻转二叉树
力扣226:翻转二叉树
13 0
|
1月前
|
算法
LeetCode[题解] 1261. 在受污染的二叉树中查找元素
LeetCode[题解] 1261. 在受污染的二叉树中查找元素
15 1
|
1月前
leetcode热题100.二叉树中的最大路径和
leetcode热题100.二叉树中的最大路径和
17 0
|
1月前
leetcode热题100. 二叉树的最近公共祖先
leetcode热题100. 二叉树的最近公共祖先
18 0
|
1月前
LeetCode-二叉树OJ题
LeetCode-二叉树OJ题
18 0
|
1月前
|
API
Leetcode-二叉树oj题
Leetcode-二叉树oj题
15 0
Leetcode-二叉树oj题
|
1月前
|
存储 Serverless 索引
二叉树的前序遍历 、二叉树的最大深度、平衡二叉树、二叉树遍历【LeetCode刷题日志】
二叉树的前序遍历 、二叉树的最大深度、平衡二叉树、二叉树遍历【LeetCode刷题日志】
|
2月前
|
存储
LeetCode题94,44,145,二叉树的前中后序遍历,非递归
LeetCode题94,44,145,二叉树的前中后序遍历,非递归
32 0
|
18天前
|
机器学习/深度学习 算法
力扣刷题日常(一)
力扣刷题日常(一)
18 2
|
1月前
|
存储 索引
《LeetCode》—— LeetCode刷题日记
《LeetCode》—— LeetCode刷题日记