1161 最大层内元素和——Leetcode天天刷【BFS】（2022.7.31）

前言

我超，到月底了，这个月的更新量好低啊， 看来是学校acm集训的强度太高了，yysy，确实有点累，996，外加上平时还有别的事情，已经快007了。。。

月末了，今天刚好又回家了，先写道题目更新一下，后面再更新质量较高的方面和内容。

题目信息

题目链接：1161. 最大层内元素和 - 力扣（LeetCode）

问题简述一下：就是对一颗二叉树，我们求其 层内最大元素和，就是对二叉树的层中，我们求元素和，然后取最大元素和的层数，如果有多层，就取层数最小的。

样例

这次不做输入和输出的处理了，因为我没在本地做测试，直接在leetcode跑了。

输入

[1,7,0,7,-8,null,null]
[989,null,10250,98693,-89388,null,null,null,-32127]
1
2

输出

2
2
1
2

提示

• 树中的节点数在 [1, 10^4]范围内
• -10^5 <= Node.val <= 10^5

从提示可以知道，最大层内元素和不超过10^(-5)，可以用这个值作为初始值。

通过图

解题思路——BFS

不玩花里胡哨的，直接BFS就好了，我们对每一层的节点，求和，然后对和进行取大更新，从而更新答案。

code（C++）

class Solution 
{
public:
	// bfs
	// 采用广度优先，我们可以直接对每一层进行遍历求值
	// 在遍历过程中，将节点的子节点加入队列中
	// 动态更新最大的层内元素和，和相对最小层
    int maxLevelSum(TreeNode* root) 
	{
		queue<TreeNode*> que;		// 队列存储节点
		int ans = 1;				// 初始化答案，默认取第一层
		int maxSum = -1e5;		// 初始化最大元素和
		que.push(root);
		int rank0 = 1;
		while(!que.empty())
		{
			// 获取当前层的节点个数
			int size = que.size();
			int sum = 0;
			while(size--)
			{
				TreeNode* node = que.front();
				que.front();
				que.pop();
				sum += node->val;		// 当前层加和
				// 如果左右子节点非空，则压入队列中
				if(node->left)
				{
					que.push(node->left);
				}
				if(node->right)
				{
					que.push(node->right);
				}
			}
			// 动态更新答案和层内最大元素和
			if(sum > maxSum)
			{
				maxSum = sum;
				ans = rank0;
			}
			++rank0;		// 下一层
		}
		
		return ans;
    }
};

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
43
44
45
46
47
48

后话

最近发生了很多事情，只能说不管多难，多要努力走下去吧，我相信，虽然路径曲折，但最终还是会走向好的方向！

前行的路上，与君共勉。