leetcode 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 。

提示：

树中的节点数为 n
2 <= n <= 105
1 <= Node.val <= 106
1 <= k <= n

思路

根据题目，要求是把所有的层的和算出来，然后看看第k大的是几，如果有相同排名，导致没有第k个，则返回-1
整个代码都是本学了1年c的菜狗写出来的，如果有可以优化的点，请大佬评论区不吝赐教~

代码

先上总代码

#include <stdlib.h>
int nowLayer = 0;
int maxLayer = 0;void findMaxLayer(struct TreeNode* node, int depth) {if (node == NULL) return;if (depth > maxLayer) maxLayer = depth;findMaxLayer(node->left, depth + 1);findMaxLayer(node->right, depth + 1);
}void searchTree(struct TreeNode* node, long long* sum)
{nowLayer++;sum[nowLayer - 1] += node->val;if(node->left != NULL){searchTree(node->left, sum);}if(node->right != NULL){searchTree(node->right, sum);}nowLayer--;return;
}int compare(const void *a, const void *b) {if (*(long long*)a < *(long long*)b) return 1;if (*(long long*)a > *(long long*)b) return -1;return 0;
}long long kthLargestLevelSum(struct TreeNode* root, int k) {findMaxLayer(root, 1); // 确定树的最大深度long long result = 0;long long *sum = (long long*)malloc(maxLayer * sizeof(long long)); // 动态确定数组长度for (int i = 0; i < maxLayer; ++i) {sum[i] = 0; // 初始化数组}searchTree(root, sum);// 对 sum 数组进行从大到小排序qsort(sum, maxLayer, sizeof(long long), compare);if(k <= maxLayer)result = sum[k - 1];free(sum); // 释放动态分配的内存return (result == 0) ? -1 : result;
}

解析

变量

int nowLayer = 0; 这个变量是用来存储当前遍历到的是第几层，方便一次遍历填充所有值。

int maxLayer = 0; 这个变量是用来存储最深层数，用来动态分配sum的大小。

刚开始做的时候想的是每个函数都要这俩变量，因此感觉全局好些，不然每个函数会变长。

long long *sum; 这个变量用来储存每一层的层和。

findMaxLayer

时间复杂度：遍历整棵树，时间复杂度为 O(n)，其中 n 是树中节点的数量。
空间复杂度：递归调用时，需要额外的栈空间，最大深度为树的高度，空间复杂度为 O(h)，其中 h 是树的高度。

这个函数是用来找最深层有多少的，因为题目给的用例不是完全二叉树，空分支的子分支是不会出现在node中的，因此10000个节点的层数假如是链表型，可能会达到5000层，因此动态分配sum数组之前需要遍历一遍。

void findMaxLayer(struct TreeNode* node, int depth) {if (node == NULL) return;if (depth > maxLayer) maxLayer = depth;findMaxLayer(node->left, depth + 1);findMaxLayer(node->right, depth + 1);
}

searchTree

算法核心，通过DFS，将树遍历一次，每一个非空的节点都将值添加到对应的layer的sum中。

时间复杂度：遍历整棵树，时间复杂度为 O(n)，其中 n 是树中节点的数量。
空间复杂度：递归调用时，需要额外的栈空间，最大深度为树的高度，空间复杂度为 O(h)，其中 h 是树的高度。另外，sum 数组的空间复杂度为 O(maxLayer)，其中 maxLayer 是树的最大深度。

void searchTree(struct TreeNode* node, long long* sum)
{nowLayer++;sum[nowLayer - 1] += node->val;if(node->left != NULL){searchTree(node->left, sum);}if(node->right != NULL){searchTree(node->right, sum);}nowLayer--;return;
}

compare

这里有个雷点，一开始我写的是

int compare(const void *a, const void *b) {return (*(long long*)a > *(long long*)b);
}

这样在跑到第43个用例的时候会出错，分析可能是因为有相同的层和，导致某个位置没有被调换。因为qsort使用的是快速排序，在 qsort 函数中，需要提供一个比较函数，该函数用于确定元素之间的顺序。比较函数需要返回一个负值、零或正值，分别表示第一个参数小于、等于或大于第二个参数。这样 qsort 就能根据比较函数的返回值来确定元素的相对顺序。我第一次给的只有1和0的返回值，没有-1，导致出了错。

正确的代码：

int compare(const void *a, const void *b) {if (*(long long*)a < *(long long*)b) return 1;if (*(long long*)a > *(long long*)b) return -1;return 0;
}

kthLargestLevelSum

题目调用的主函数

先获取最深层数，

long long kthLargestLevelSum(struct TreeNode* root, int k) {findMaxLayer(root, 1); // 确定树的最大深度long long result = 0;long long *sum = (long long*)malloc(maxLayer * sizeof(long long)); // 动态确定数组长度for (int i = 0; i < maxLayer; ++i) {sum[i] = 0; // 初始化数组}searchTree(root, sum);// 对 sum 数组进行从大到小排序qsort(sum, maxLayer, sizeof(long long), compare);if(k <= maxLayer)result = sum[k - 1];free(sum); // 释放动态分配的内存return (result == 0) ? -1 : result;
}

结果

另外贴一个官方题解

广度优先搜索 + 排序

思路

（这种题目一般dfs不用动脑，bfs还得分析。。）

先使用广度优先搜索计算出树的每一层的节点值的和，保存在数组 levelSumArray\textit{levelSumArray}levelSumArray 中。然后将数组进行排序，返回第 kkk 大的值。需要考虑数组长度小于 kkk 的边界情况。也可以使用快速选择的算法快速定位第 kkk 大的元素。

代码

#define MAX_NODE_SIZE 100000static long long cmp(const void *a, const void *b) {long long sub = *(long long *)a - *(long long *)b;return sub < 0 ? -1 : 1;
}long long kthLargestLevelSum(struct TreeNode* root, int k) {struct TreeNode **q = (struct TreeNode **)malloc(sizeof(struct TreeNode *) * MAX_NODE_SIZE);long long *levelSumArray = (long long *)malloc(sizeof(long long) * MAX_NODE_SIZE);int head = 0, tail = 0;int pos = 0;q[tail++] = root;while (head != tail) {long long levelSum = 0, size = tail - head;for (int i = 0; i < size; i++) {struct TreeNode *node = q[head];head++;levelSum += node->val;if (node->left) {q[tail++] = node->left;}if (node->right) {q[tail++] = node->right;}}levelSumArray[pos++] = levelSum;}if (pos < k) {return -1;}qsort(levelSumArray, pos, sizeof(long long), cmp);return levelSumArray[pos - k];
}作者：力扣官方题解
链接：https://leetcode.cn/problems/kth-largest-sum-in-a-binary-tree/solutions/2645278/er-cha-shu-zhong-de-di-k-da-ceng-he-by-l-948i/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。