Skip to content

1161. Maximum Level Sum of a Binary Tree 👍

Approach 1: BFS

  • Time: $O(n)$
  • Space: $O(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
27
class Solution {
 public:
  int maxLevelSum(TreeNode* root) {
    int ans = 0;
    int maxLevelSum = INT_MIN;
    queue<TreeNode*> q{{root}};

    for (int level = 1; !q.empty(); ++level) {
      int levelSum = 0;
      for (int sz = q.size(); sz > 0; --sz) {
        TreeNode* node = q.front();
        q.pop();
        levelSum += node->val;
        if (node->left != nullptr)
          q.push(node->left);
        if (node->right != nullptr)
          q.push(node->right);
      }
      if (levelSum > maxLevelSum) {
        maxLevelSum = levelSum;
        ans = level;
      }
    }

    return ans;
  }
};

 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
class Solution {
  public int maxLevelSum(TreeNode root) {
    int ans = 0;
    int maxLevelSum = Integer.MIN_VALUE;
    Queue<TreeNode> q = new LinkedList<>(Arrays.asList(root));

    for (int level = 1; !q.isEmpty(); ++level) {
      int levelSum = 0;
      for (int sz = q.size(); sz > 0; --sz) {
        TreeNode node = q.poll();
        levelSum += node.val;
        if (node.left != null)
          q.offer(node.left);
        if (node.right != null)
          q.offer(node.right);
      }
      if (levelSum > maxLevelSum) {
        maxLevelSum = levelSum;
        ans = level;
      }
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def maxLevelSum(self, root: Optional[TreeNode]) -> int:
    ans = 0
    maxLevelSum = -math.inf
    q = collections.deque([root])

    level = 1
    while q:
      levelSum = 0
      for _ in range(len(q)):
        node = q.popleft()
        levelSum += node.val
        if node.left:
          q.append(node.left)
        if node.right:
          q.append(node.right)
      if levelSum > maxLevelSum:
        maxLevelSum = levelSum
        ans = level
      level += 1

    return ans

Approach 2: DFS

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int maxLevelSum(TreeNode* root) {
    // levelSums[i] := the sum of level (i + 1) (1-indexed)
    vector<int> levelSums;
    dfs(root, 0, levelSums);
    return 1 + ranges::max_element(levelSums) - levelSums.begin();
  }

 private:
  void dfs(TreeNode* root, int level, vector<int>& levelSums) {
    if (root == nullptr)
      return;
    if (levelSums.size() == level)
      levelSums.push_back(0);
    levelSums[level] += root->val;
    dfs(root->left, level + 1, levelSums);
    dfs(root->right, level + 1, levelSums);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public int maxLevelSum(TreeNode root) {
    // levelSums[i] := the sum of level (i + 1) (1-indexed)
    List<Integer> levelSums = new ArrayList<>();
    dfs(root, 0, levelSums);
    return 1 + IntStream.range(0, levelSums.size())
                   .reduce(0, (a, b) -> levelSums.get(a) < levelSums.get(b) ? b : a);
  }

  private void dfs(TreeNode root, int level, List<Integer> levelSums) {
    if (root == null)
      return;
    if (levelSums.size() == level)
      levelSums.add(0);
    levelSums.set(level, levelSums.get(level) + root.val);
    dfs(root.left, level + 1, levelSums);
    dfs(root.right, level + 1, levelSums);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def maxLevelSum(self, root: Optional[TreeNode]) -> int:
    # levelSums[i] := the sum of level (i + 1) (1-indexed)
    levelSums = []

    def dfs(root: Optional[TreeNode], level: int) -> None:
      if not root:
        return
      if len(levelSums) == level:
        levelSums.append(0)
      levelSums[level] += root.val
      dfs(root.left, level + 1)
      dfs(root.right, level + 1)

    dfs(root, 0)
    return 1 + levelSums.index(max(levelSums))