说在前面
🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。
题目描述
给你一棵二叉树的根节点 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 。
提示：
- 树中的节点数为
n 2 <= n <= 10^51 <= Node.val <= 10^61 <= k <= n
解题思路
首先我们需要先理解一下题意，题目要我们计算的是树的层和，如下图：
我们需要先计算出每一层的节点和，涉及到层级的话我们可以用层序遍历来解决题目：
- 层序遍历通常使用队列（Queue）来实现。算法的基本思想是：
- 1、将根节点入队。
- 2、循环执行以下步骤直到队列为空：
- 从队列中取出一个节点，并访问该节点。
- 将该节点的子节点（如果有）依次入队。
通过这种方式，可以确保按照层级顺序逐层访问树的所有节点。层序遍历是一种广度优先搜索（Breadth-First Search，BFS）的应用，适用于需要按照层级结构处理树的问题。
获取到每一层级的节点和之后，我们进行排序找出第k大的和即可。
AC代码
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @param {number} k * @return {number} */ var kthLargestLevelSum = function (root, k) { const q = [{ node: root, floor: 1 }]; const cnt = []; let ind = 0; while (ind < q.length) { const { node, floor } = q[ind]; if (cnt.length < floor) cnt.push(0); cnt[floor - 1] += node.val; if (node.left) q.push({ node: node.left, floor: floor + 1 }); if (node.right) q.push({ node: node.right, floor: floor + 1 }); ind++; } if (cnt.length < k) return -1; return cnt.sort((a, b) => b - a)[k - 1]; };
公众号
关注公众号『前端也能这么有趣』，获取更多有趣内容。
说在后面
🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『
前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。
