难度: Medium
给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。
请返回层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。
示例 1：
输入：root = [1,7,0,7,-8,null,null] 输出：2 解释： 第 1 层各元素之和为 1， 第 2 层各元素之和为 7 + 0 = 7， 第 3 层各元素之和为 7 + -8 = -1， 所以我们返回第 2 层的层号，它的层内元素之和最大。
示例 2：
输入：root = [989,null,10250,98693,-89388,null,null,null,-32127] 输出：2
提示：
[1, 104]范围内-105 <= Node.val <= 105运行时间: 132 ms
内存: 19.6 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxLevelSum(self, root: Optional[TreeNode]) -> int:
ans, maxSum = 1, root.val
level, q = 1, [root]
while q:
sum, nq = 0, []
for node in q:
sum += node.val
if node.left:
nq.append(node.left)
if node.right:
nq.append(node.right)
if sum > maxSum:
ans, maxSum = level, sum
q = nq
level += 1
return ans
该题解使用了广度优先搜索（BFS）来遍历二叉树的每一层，并计算每一层的节点值之和。算法初始化时，将二叉树的根节点放入队列中。在每一次循环中，算法处理当前队列中的所有节点（即当前层的所有节点），计算这一层的总和，并将其子节点放入下一个队列中，为处理下一层做准备。同时，算法比较当前层的总和与之前记录的最大层的总和，如果当前层的总和更大，则更新最大总和和对应的层号。这一过程持续进行，直到所有层都被处理完毕。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxLevelSum(self, root: Optional[TreeNode]) -> int:
ans, maxSum = 1, root.val # 初始化最大层号为1，最大和为根节点的值
level, q = 1, [root] # 初始化层号为1，队列q用来存储当前层的节点
while q: # 当队列不为空时
sum, nq = 0, [] # 初始化当前层的和为0，nq为下一层的节点列表
for node in q: # 遍历当前层所有节点
sum += node.val # 累加当前节点的值到sum
if node.left: # 如果左子节点存在，加入下一层节点列表
nq.append(node.left)
if node.right: # 如果右子节点存在，也加入下一层节点列表
nq.append(node.right)
if sum > maxSum: # 如果当前层的和大于之前记录的最大和
ans, maxSum = level, sum # 更新最大和及对应的层号
q = nq # 更新队列为下一层的节点列表
level += 1 # 层号递增
return ans # 返回最大和对应的层号
算法会正常计算这一层所有节点值的总和，即使它们都是负数。然后，它将这一层的总和与之前记录的最大总和进行比较。如果这一层的总和大于目前记录的最大总和，则更新最大总和及对应的层号。如果所有层的总和都是负数，算法仍然会返回具有最大（或者说最不负）总和的层号。
使用广度优先搜索（BFS）可以自然地按层遍历树。这种方法可以让我们简单地在每一层的遍历过程中计算出该层的总和，并轻松更新和比较最大层总和。相对地，深度优先搜索（DFS）需要额外的机制来跟踪节点的层次信息，并且在遍历过程中不断回溯，这会使层次总和的计算和比较变得更加复杂。
在每一次循环中，算法首先创建一个空的队列nq用来存放下一层的节点。然后，它遍历当前队列q中的所有节点，并将它们的子节点（如果存在）加入到nq中。这确保了当当前层的所有节点被处理完后，nq包含了下一层的所有节点。之后，将q更新为nq，继续下一轮循环，这样每次循环处理的都是同一层的所有节点。
算法在比较层的总和时，只有当找到一个更大的总和时才会更新记录的最大总和和对应的层号。如果当前层的总和与之前记录的最大总和相等，它不会更新层号。这意味着最初记录的那个层号（最小的层号）将被保留，直到找到一个具有更大总和的层。因此，算法自然地保证了在多个层的总和相等时返回最小的层号。