【LeetCode】1161. 最大层内元素和

题目

1161. 最大层内元素和

给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。

请返回层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。

示例 1：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yK3DGt66-1659234515466)(figures/1161. 最大层内元素和/capture.jpeg)]

输入：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

思路

• 遍历每一层 ，求和，判断是否为最大值，若为最大值则记录最大值和层号

代码

# 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:
        maxSum,layer,currentLayer = -1<<31,0,0
        queue = collections.deque([root])
        while queue:
            currentSum = 0
            currentLayer += 1
            for _ in range(len(queue)):
                cur = queue.popleft()
                currentSum += cur.val
                if cur.left: queue.append(cur.left)
                if cur.right: queue.append(cur.right)
            if currentSum>maxSum:
                maxSum,layer = currentSum,currentLayer
        return layer

复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$