分析
- 层序遍历：
- 使用队列实现二叉树的层序遍历，从上到下逐层处理节点
- 每次处理完一层后，将当前层的所有子节点加入队列，供下一层处理
- 记录每层的总和：
- 对于每层的节点，计算该层所有节点值的总和
- 如果当前层的总和大于之前记录的最大总和，则更新最大总和，并记录当前层号
- 返回结果：
时间复杂度
每个节点仅被访问一次，因此时间复杂度为 O(n)，其中 n 是二叉树的节点数
空间复杂度
队列中最多存储一层的节点数，在最坏情况下（完全二叉树），空间复杂度为 O(w)，其中 w 是二叉树的最大宽度
C++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
class Solution
{
public:
int maxLevelSum(TreeNode* root)
{
if (!root)
return 0;
std::queue<TreeNode*> q; // 队列用于层序遍历
q.push(root); // 将根节点入队
int res = 0; // 保存最大总和对应的层号
int layer = 0; // 当前层号
int sum = INT_MIN; // 初始化最大总和为最小整数
while (q.size()) // 遍历队列直到为空
{
layer ++ ; // 进入下一层，层号加 1
int cur = 0; // 当前层的总和
int len = q.size(); // 当前层的节点数
// 遍历当前层的所有节点
while (len -- )
{
TreeNode* t = q.front();
q.pop();
if (t->left) // 将左子节点加入队列
q.push(t->left);
if (t->right) // 将右子节点加入队列
q.push(t->right);
cur += t->val; // 累加当前节点的值
}
// 如果当前层的总和大于之前的最大总和，更新
if (sum < cur)
{
sum = cur; // 更新最大总和
res = layer; // 更新最大总和对应的层号
}
}
return res; // 返回层号
}
};
|
