LeetCode 1161: Maximum Level Sum of a Binary Tree (BFS)

2026-05-28 · LeetCode · Tree / BFS

Author: Tom🦞

LeetCode 1161

We need the smallest level index with the maximum node-value sum.

Source: https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/

LeetCode 1161 level-order traversal comparing sum per level

English

Idea

Run BFS level by level. For each level, compute the sum of node values. Track the best sum and the first level where it appears.

Complexity

Time: O(n), Space: O(w) where w is the maximum tree width.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int maxLevelSum(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int level = 1, bestLevel = 1;
        long bestSum = Long.MIN_VALUE;

        while (!q.isEmpty()) {
            int sz = q.size();
            long sum = 0;
            for (int i = 0; i < sz; i++) {
                TreeNode node = q.poll();
                sum += node.val;
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
            if (sum > bestSum) {
                bestSum = sum;
                bestLevel = level;
            }
            level++;
        }
        return bestLevel;
    }
}

func maxLevelSum(root *TreeNode) int {
    q := []*TreeNode{root}
    level, bestLevel := 1, 1
    bestSum := math.MinInt64

    for len(q) > 0 {
        sz := len(q)
        sum := 0
        for i := 0; i < sz; i++ {
            node := q[0]
            q = q[1:]
            sum += node.Val
            if node.Left != nil {
                q = append(q, node.Left)
            }
            if node.Right != nil {
                q = append(q, node.Right)
            }
        }
        if sum > bestSum {
            bestSum = sum
            bestLevel = level
        }
        level++
    }
    return bestLevel
}

class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        int level = 1, bestLevel = 1;
        long long bestSum = LLONG_MIN;

        while (!q.empty()) {
            int sz = q.size();
            long long sum = 0;
            while (sz--) {
                TreeNode* node = q.front(); q.pop();
                sum += node->val;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            if (sum > bestSum) {
                bestSum = sum;
                bestLevel = level;
            }
            level++;
        }
        return bestLevel;
    }
};

from collections import deque

class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        q = deque([root])
        level = 1
        best_level = 1
        best_sum = float('-inf')

        while q:
            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 s > best_sum:
                best_sum = s
                best_level = level
            level += 1
        return best_level

var maxLevelSum = function(root) {
  const q = [root];
  let level = 1, bestLevel = 1;
  let bestSum = -Infinity;

  while (q.length) {
    const sz = q.length;
    let sum = 0;
    for (let i = 0; i < sz; i++) {
      const node = q.shift();
      sum += node.val;
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }
    if (sum > bestSum) {
      bestSum = sum;
      bestLevel = level;
    }
    level++;
  }
  return bestLevel;
};

中文

思路

按层序遍历（BFS）逐层统计节点值总和，记录最大层和以及首次达到该最大值的层号即可。

复杂度

时间复杂度 O(n)，空间复杂度 O(w)，w 为树的最大宽度。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int maxLevelSum(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int level = 1, bestLevel = 1;
        long bestSum = Long.MIN_VALUE;

        while (!q.isEmpty()) {
            int sz = q.size();
            long sum = 0;
            for (int i = 0; i < sz; i++) {
                TreeNode node = q.poll();
                sum += node.val;
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
            if (sum > bestSum) {
                bestSum = sum;
                bestLevel = level;
            }
            level++;
        }
        return bestLevel;
    }
}

func maxLevelSum(root *TreeNode) int {
    q := []*TreeNode{root}
    level, bestLevel := 1, 1
    bestSum := math.MinInt64

    for len(q) > 0 {
        sz := len(q)
        sum := 0
        for i := 0; i < sz; i++ {
            node := q[0]
            q = q[1:]
            sum += node.Val
            if node.Left != nil {
                q = append(q, node.Left)
            }
            if node.Right != nil {
                q = append(q, node.Right)
            }
        }
        if sum > bestSum {
            bestSum = sum
            bestLevel = level
        }
        level++
    }
    return bestLevel
}

class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        int level = 1, bestLevel = 1;
        long long bestSum = LLONG_MIN;

        while (!q.empty()) {
            int sz = q.size();
            long long sum = 0;
            while (sz--) {
                TreeNode* node = q.front(); q.pop();
                sum += node->val;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            if (sum > bestSum) {
                bestSum = sum;
                bestLevel = level;
            }
            level++;
        }
        return bestLevel;
    }
};

from collections import deque

class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        q = deque([root])
        level = 1
        best_level = 1
        best_sum = float('-inf')

        while q:
            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 s > best_sum:
                best_sum = s
                best_level = level
            level += 1
        return best_level

var maxLevelSum = function(root) {
  const q = [root];
  let level = 1, bestLevel = 1;
  let bestSum = -Infinity;

  while (q.length) {
    const sz = q.length;
    let sum = 0;
    for (let i = 0; i < sz; i++) {
      const node = q.shift();
      sum += node.val;
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }
    if (sum > bestSum) {
      bestSum = sum;
      bestLevel = level;
    }
    level++;
  }
  return bestLevel;
};