🌲 初学者友好指南 “Maximum Level Sum of a Binary Tree” – LeetCode 1161 (C++, Python, JavaScript)

Source: Dev.to

请提供您希望翻译的完整文本内容（除代码块和 URL 之外），我将为您将其翻译成简体中文并保持原有的 Markdown 格式。

Source:

问题概述

给定一棵二叉树的 根节点，每个节点存储一个整数值。
根节点位于 第 1 层，它的子节点位于 第 2 层，以此类推。

目标：
返回节点值之和 最大的层号。
如果有多个层的和相同且为最大值，返回 最小的（即最高的）层号。

示例

Input:  root = [1,7,0,7,-8,null,null]
Output: 2
Explanation:
Level 1 sum = 1
Level 2 sum = 7 + 0 = 7
Level 3 sum = 7 + (-8) = -1
→ The maximum sum is 7, occurring at level 2.

直觉

检查树的最自然方式是 逐层（level by level） 进行 广度优先搜索（BFS）。
BFS 不会深入单个分支，而是使用 队列 在进入下一层之前处理当前“层”上的所有节点。

算法概述

1. 初始化 一个包含根节点的队列。
2. 当队列不为空时：
   • 记录当前队列大小 → 该层的节点数。
   • 逐个出队节点，将其值加入累计的 levelSum，并将其非空子节点入队。
   • 该层处理完毕后，将 levelSum 与迄今为止的最大和进行比较，如有必要更新答案。
3. 返回产生最大和的层索引。

BFS 保证 O(N) 的时间复杂度（每个节点访问一次）和 O(W) 的额外空间，其中 W 是树的最大宽度（即最大层的节点数）。

代码块

C++

class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        if (!root) return 0;

        long long maxSum   = LLONG_MIN;   // handles negative values
        int       maxLevel = 1;
        int       curLevel = 1;

        queue q;
        q.push(root);

        while (!q.empty()) {
            int   sz       = q.size();
            long long levelSum = 0;

            for (int i = 0; i val;

                if (node->left)  q.push(node->left);
                if (node->right) q.push(node->right);
            }

            if (levelSum > maxSum) {
                maxSum   = levelSum;
                maxLevel = curLevel;
            }
            ++curLevel;
        }
        return maxLevel;
    }
};

Python

from collections import deque
# 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:
        if not root:
            return 0

        max_sum   = float('-inf')
        max_level = 1
        cur_level = 1

        q = deque([root])

        while q:
            level_sum = 0
            for _ in range(len(q)):
                node = q.popleft()
                level_sum += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)

            if level_sum > max_sum:
                max_sum   = level_sum
                max_level = cur_level

            cur_level += 1

        return max_level

JavaScript

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxLevelSum = function (root) {
    if (!root) return 0;

    let maxSum   = -Infinity;
    let maxLevel = 1;
    let curLevel = 1;

    const queue = [root];

    while (queue.length) {
        const levelSize = queue.length;
        let levelSum = 0;

        for (let i = 0; i  maxSum) {
            maxSum   = levelSum;
            maxLevel = curLevel;
        }
        ++curLevel;
    }

    return maxLevel;
};

关键要点

• 广度优先搜索 (BFS) 是处理“层序”树问题的首选技术。
• 队列（或 Python 中的 deque）让我们能够以每个节点摊销 O(1) 的时间处理每一层。
• 由于节点值可能为负数，需将“最大和”初始化为可能的最小值（LLONG_MIN、-Infinity 或 -inf）。
• 时间复杂度：O(N)，其中 N 为节点数。
• 空间复杂度：O(W)，其中 W 为树的最大宽度（完全平衡树的最坏情况为 O(N)）。

最后思考

这个问题是对大规模系统中出现的树遍历模式的极佳入门：

• 搜索引擎索引 通常使用类似 BFS 的爬虫，从主页逐层探索页面，确保最“重要”（顶层）的内容优先处理。
• 在 社交网络分析 中，定位活动最多的层级对应“最大层级和”的概念——识别最具影响力的用户“层”。

掌握 BFS 和队列管理能够帮助你应对各种真实世界的图和树挑战。祝编码愉快！

识别最有前景的分离度

识别哪个 “分离度” 包含最多潜在连接是图分析中的关键步骤。掌握 广度优先搜索 (BFS) 是在 Google 或 Meta 等公司技术面试的核心要求。