What is the main pattern for solving Maximum Level Sum of a Binary Tree?

The main pattern involves binary-tree traversal and state tracking. Typically, BFS is used to process nodes level by level while calculating their sums.

How do I calculate the sum for each level?

To calculate the sum at each level, perform a BFS traversal and keep track of the nodes at each level, summing their values as you process each level.

What should I do if multiple levels have the same sum?

If multiple levels have the same sum, return the smallest level number as specified in the problem statement.

Can this problem be solved using DFS?

While DFS can be used, BFS is generally more efficient for this problem as it directly processes nodes level by level, which aligns with the problem requirements.

What is the time complexity of this problem?

The time complexity is O(n), where n is the number of nodes in the tree, as each node is visited exactly once during the traversal.

#1161

Medium

auto_awesome二分·树·traversal

LeetCode 题解工作台

最大层内元素和

给你一个二叉树的根节点 root 。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。返回总和最大的那一层的层号 x 。如果有多层的总和一样大，返回其中最小的层号 x 。示例 1：输入： root = [1,7,0,7,-8,null,null] 输出： 2 解…

树深度优先搜索广度优先搜索二叉树

题目描述

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

返回总和最大的那一层的层号 x。如果有多层的总和一样大，返回其中最小的层号 x。

示例 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, 10⁴]范围内
-10⁵ <= Node.val <= 10⁵

lightbulb

解题思路

方法一：BFS

BFS 层次遍历，求每一层的节点和，找出节点和最大的层，若有多个层的节点和最大，则返回最小的层。

具体地，我们使用一个队列 $q$ 来存储当前层的节点。每次遍历时，我们记录当前层的节点和 $s$ ，然后将当前层的所有节点的子节点加入队列中，准备遍历下一层。我们使用变量 $mx$ 来记录当前最大的节点和，使用变量 $ans$ 来记录对应的层号。每次计算完一层的节点和后，如果 $s$ 大于 $mx$ ，则更新 $mx$ 和 $ans$ 。最后返回 $ans$ 即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为二叉树的节点数。

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

# 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:
        q = deque([root])
        mx = -inf
        i = 0
        while q:
            i += 1
            s = 0
            for _ in range(len(q)):
                node = q.popleft()
                s += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            if mx < s:
                mx = s
                ans = i
        return ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Candidate correctly identifies that BFS is the most suitable approach for level-order traversal.
question_mark
Candidate demonstrates understanding of state tracking while performing BFS to calculate sums.
question_mark
Candidate handles multiple levels with the same sum, returning the smallest level.

warning

常见陷阱

外企场景

error
Failing to account for the case where multiple levels have the same sum and not returning the smallest level.
error
Incorrectly calculating the sum for each level, leading to the wrong level being returned.
error
Using an inefficient traversal method like DFS, which may not handle large trees as well as BFS in this case.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to return the level with the smallest sum rather than the largest.
arrow_right_alt
Instead of returning the level number, return the sum at the level with the maximum sum.
arrow_right_alt
Handle edge cases with trees that only contain one node, returning level 1.

help

常见问题

外企场景

继续练习

#1123 最深叶节点的最近公共祖先 #1261 在受污染的二叉树中查找元素 #1302 层数最深叶子节点的和