[面试题] 从某节10-10工作制跑路，到二叉树“最大层内元素和”题解

刚看到一个帖子，内容是说朋友从某互联网大厂离职了，原因是工作强度太大，每天从早上10点干到晚上10点。入职还不到三个星期就走了，发帖人还担心朋友会不会因此被公司拉黑简历。

我也翻看了一下网友的回复，有的说她“抗压能力不行”，也有的吐槽大厂“强度离谱”。在我看来，这件事很难简单地去评判谁对谁错。10-10-6的工作节奏，本来就不是每个人都能适应的，她尝试后发现无法承受，及时止损，本身就是对自己负责的一种表现。如果硬撑下去，身体垮了或者情绪崩溃，后果又由谁来承担呢？

至于担心简历被拉黑，我觉得或许没必要过于放大。互联网大厂并非仅此一家，平台在选人，人也在选平台。如果不适应这种高强度的工作模式，早点离开总比混日子、消耗自己要好。真正看重你能力的团队，会关注你的技术积累和成长潜力，而不会过分纠结于那“短短三个星期”的经历。

归根结底，职场上最重要的是认清自己能接受的节奏和底线，并为自己的选择承担相应的后果。职业生涯路还很长，只要人还在持续成长，机会总会有的。

---

算法题：最大层内元素和

昨天深夜十一点多，我在公司楼下啃着个凉掉的汉堡，同事小李跑过来跟我说：“东哥，我刷题刷到头大，那道‘最大层内元素和’的题，你能不能给我讲讲思路？”

我脑子里过了一下，嗯，这题很典型，属于“会了思路两分钟写完，没思路一小时都转不出来”的那种。

题目叫“最大层内元素和”，场景可以这样理解：给定一棵二叉树，每一层都有若干节点，每个节点都有一个整数值。

你需要做的就一件事：

计算每一层所有节点值的总和，找出和最大的那一层，最后返回该层的“层号”（规定根节点在第1层）。

举一个特别简单的例子，手动算一下就明白了：

• 第一层：只有根节点 1，和是 1
• 第二层：节点 2 和 3，和是 5
• 第三层：节点 4, 5, 6, 7，和是 22

那么答案显然就是第 3 层。

所以，这道题的本质就是：按层遍历这棵树，计算每一层的节点值之和，同时记录下我们遇到过的最大和及其对应的层号。这么一说，是不是感觉没那么吓人了？

我当时就对小李说：你别一上来就想着递归或者什么高深算法，先用最符合直觉的方式去思考。

普通人要数一栋楼每层有多少人，是不是也得一层一层地往下数？这道题一模一样，使用层序遍历（BFS） 就能完美解决。大致的流程如下：

1. 准备一个队列，先把根节点放进去。
2. 定义两个变量：max_sum 记录“当前遇到的最大层和”；ans_level 记录这个和对应的层号。
3. 每一轮循环，从队列里“批量”取出当前层的所有节点：
   • 把这些节点的值累加起来，得到当前层的和 cur_sum。
   • 把这些节点的左右孩子（如果存在）放入队列，为下一层的遍历做准备。
4. 比较当前层的和 cur_sum 是否大于 max_sum，如果更大，就更新 max_sum 和 ans_level。
5. 重复步骤3和4，直到队列为空。

整个过程只遍历树的所有节点一次，时间复杂度是 O(n)，非常直接。

我按 LeetCode 的标准写法来实现，TreeNode 这个节点类就假定已经存在：

# 二叉树节点的定义（LeetCode 标配）
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: TreeNode) -> int:
        # 边界情况，空树
        if not root:
            return 0

        from collections import deque
        q = deque()
        q.append(root)

        level = 1  # 当前是第几层
        max_sum = float('-inf')
        ans_level = 1

        while q:
            size = len(q)    # 当前这一层有多少个节点
            cur_sum = 0

            # 把这一层的节点一个个拿出来
            for _ in range(size):
                node = q.popleft()
                cur_sum += node.val

                # 把下一层的孩子排队
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)

            # 看看这一层是不是目前最大的
            if cur_sum > max_sum:
                max_sum = cur_sum
                ans_level = level

            level += 1

        return ans_level

注意几个关键点：

• size = len(q) 这一步至关重要，它保证了内部的 for 循环只处理当前这一层的节点。
• 处理完当前层所有节点后，再统一将它们的子节点推入队列，保证了层次分明。
• 每一层结束时，比较并更新一次最大值和层号。

这个套路非常实用，以后遇到诸如“按层统计”、“每层平均值”、“每层最大值”这类问题，基本都可以照此办理。

小李又问：那能用递归（DFS）做吗？我说当然可以，不过递归版本对于新手来说，可能更容易写得绕来绕去。

大致的思路是：在用 DFS 向下遍历时，把当前所在的层号 level 作为参数传递下去。同时使用一个列表或字典来记录每一层的累加和。等整个遍历完成后，再从这个记录里找出和最大的层。

代码可以看一下，但建议先把 BFS 版本写熟练：

class Solution:
    def maxLevelSum(self, root: TreeNode) -> int:
        # 用一个列表记录每层的和，index = level - 1
        level_sums = []

        def dfs(node: TreeNode, level: int):
            if not node:
                return
            # 如果是新的一层，先扩容列表
            if level > len(level_sums):
                level_sums.append(0)
            level_sums[level - 1] += node.val

            dfs(node.left, level + 1)
            dfs(node.right, level + 1)

        dfs(root, 1)

        # 找出最大和所在的层（注意索引转层号要 +1）
        max_sum = max(level_sums)
        return level_sums.index(max_sum) + 1

DFS 版本的代码看起来更简短，但对初学者可能不太友好：你需要在大脑中模拟递归调用栈以及层号的变化过程。

无论是 BFS 还是 DFS，时间复杂度都是 O(n)，其中 n 是节点数，因为每个节点只被访问一次。

空间复杂度方面，BFS 最坏情况下队列需要存储一层的所有节点，也是 O(n)。DFS 版本的空间消耗主要在递归调用栈上，最坏情况（树退化成链表）也是 O(n)，对于平衡二叉树则是 O(h)，h 是树的高度。

掌握这些算法与数据结构的核心思路，在面试中被问到相关问题时，就能有条不紊地解释清楚，而不需要死记硬背。

在技术成长的路上，除了刷题，多与同行交流、分享实战经验也至关重要。欢迎来云栈社区逛逛，这里聚集了许多乐于分享的开发者，或许你能找到更多启发和共鸣。