【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();
        }
    }
}
相关文章
|
3月前
|
分布式计算 算法 Go
【LeetCode 热题100】BFS/DFS 实战:岛屿数量 & 腐烂的橘子(力扣200 / 994 )(Go语言版)
本文讲解了两道经典的图论问题:**岛屿数量(LeetCode 200)** 和 **腐烂的橘子(LeetCode 994)**,分别通过 DFS/BFS 实现。在“岛屿数量”中,利用深度或广度优先搜索遍历二维网格,标记连通陆地并计数;“腐烂的橘子”则采用多源 BFS,模拟腐烂传播过程,计算最短时间。两者均需掌握访问标记技巧,是学习网格搜索算法的绝佳实践。
137 1
|
4月前
|
Go 开发者 索引
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣33 / 81/ 153/154)(Go语言版)
本文深入探讨了LeetCode中四道关于「搜索旋转排序数组」的经典题目,涵盖了无重复和有重复元素的情况。通过二分查找的变形应用,文章详细解析了每道题的解题思路和Go语言实现代码。关键点包括判断有序区间、处理重复元素以及如何缩小搜索范围。文章还总结了各题的异同,并推荐了类似题目,帮助读者全面掌握二分查找在旋转数组中的应用。无论是初学者还是有经验的开发者,都能从中获得实用的解题技巧和代码实现方法。
253 14
|
3月前
|
Go
【LeetCode 热题100】BFS/DFS 实战:岛屿数量 & 腐烂的橘子(力扣200 / 994 )(Go语言版)
本篇博客详细解析了三道经典的动态规划问题:198. 打家劫舍(线性状态转移)、279. 完全平方数与322. 零钱兑换(完全背包问题)。通过 Go 语言实现,帮助读者掌握动态规划的核心思想及其实战技巧。从状态定义到转移方程,逐步剖析每道题的解法,并总结其异同点,助力解决更复杂的 DP 问题。适合初学者深入理解动态规划的应用场景和优化方法。
81 0
|
5月前
|
Go
【LeetCode 热题100】路径与祖先:二叉树中的深度追踪技巧(力扣437 / 236 )(Go语言版)
本文深入探讨二叉树中路径与祖先问题,涵盖两道经典题目:LeetCode 437(路径总和 III)和236(最近公共祖先)。对于路径总和 III,文章分析了双递归暴力解法与前缀和优化方法,后者通过哈希表记录路径和,将时间复杂度从O(n²)降至O(n)。在最近公共祖先问题中,采用后序遍历递归查找,利用“自底向上”的思路确定最近公共祖先节点。文中详细解析代码实现与核心要点,帮助读者掌握深度追踪技巧,理解树结构中路径与节点关系的本质。这类问题在面试中高频出现,掌握其解法意义重大。
114 4
|
5月前
|
算法 Go
【LeetCode 热题100】深入理解二叉树结构变化与路径特性(力扣104 / 226 / 114 / 543)(Go语言版)
本博客深入探讨二叉树的深度计算、结构变换与路径分析,涵盖四道经典题目:104(最大深度)、226(翻转二叉树)、114(展开为链表)和543(二叉树直径)。通过递归与遍历策略(前序、后序等),解析每题的核心思路与实现方法。结合代码示例(Go语言),帮助读者掌握二叉树相关算法的精髓。下一讲将聚焦二叉树构造问题,欢迎持续关注!
131 10
|
5月前
|
存储 算法 数据可视化
【二叉树遍历入门:从中序遍历到层序与右视图】【LeetCode 热题100】94:二叉树的中序遍历、102:二叉树的层序遍历、199:二叉树的右视图(详细解析)(Go语言版)
本文详细解析了二叉树的三种经典遍历方式:中序遍历(94题)、层序遍历(102题)和右视图(199题)。通过递归与迭代实现中序遍历,深入理解深度优先搜索(DFS);借助队列完成层序遍历和右视图,掌握广度优先搜索(BFS)。文章对比DFS与BFS的思维方式,总结不同遍历的应用场景,为后续构造树结构奠定基础。
260 10
|
5月前
|
Go 索引 Perl
【LeetCode 热题100】【二叉树构造题精讲:前序 + 中序建树 & 有序数组构造 BST】(详细解析)(Go语言版)
本文详细解析了二叉树构造的两类经典问题:通过前序与中序遍历重建二叉树(LeetCode 105),以及将有序数组转化为平衡二叉搜索树(BST,LeetCode 108)。文章从核心思路、递归解法到实现细节逐一拆解,强调通过索引控制子树范围以优化性能,并对比两题的不同构造逻辑。最后总结通用构造套路,提供进阶思考方向,帮助彻底掌握二叉树构造类题目。
276 9
|
11月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
87 0
|
11月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
70 0
|
11月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
87 0