Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1161.html

1161. Maximum Level Sum of a Binary Tree (Medium)

Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.

Return the smallest level X such that the sum of all the values of nodes at level X is maximal.

 

Example 1:

Input: [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.
So we return the level with the maximum sum which is level 2.

 

Note:

1. The number of nodes in the given tree is between 1 and 10^4.
2. -10^5 <= node.val <= 10^5

Companies:
Google

Related Topics:
Graph

Solution 1. Level-order Traversal

// OJ: https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        if (!root) return 0;
        int maxSum = 0, ans = 0, lv = 1;
        queue<TreeNode*> q;
        q.push(root);
        while (q.size()) {
            int cnt = q.size(), sum = 0;
            while (cnt--) {
                auto node = q.front();
                q.pop();
                sum += node->val;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            if (sum > maxSum) {
                maxSum = sum;
                ans = lv;
            }
            ++lv;
        }
        return ans;
    }
};

Java

• Java
• C++
• Python

• /**
   * Definition for a binary tree node.
   * public class TreeNode {
   *     int val;
   *     TreeNode left;
   *     TreeNode right;
   *     TreeNode(int x) { val = x; }
   * }
   */
  class Solution {
      public int maxLevelSum(TreeNode root) {
          if (root == null)
              return 0;
          int maxSum = 0;
          int maxSumLevel = 0;
          int level = 0;
          Queue<TreeNode> queue = new LinkedList<TreeNode>();
          queue.offer(root);
          while (!queue.isEmpty()) {
              level++;
              int curSum = 0;
              int size = queue.size();
              for (int i = 0; i < size; i++) {
                  TreeNode node = queue.poll();
                  curSum += node.val;
                  TreeNode left = node.left, right = node.right;
                  if (left != null)
                      queue.offer(left);
                  if (right != null)
                      queue.offer(right);
              }
              if (curSum > maxSum) {
                  maxSum = curSum;
                  maxSumLevel = level;
              }
          }
          return maxSumLevel;
      }
  }
  

• // OJ: https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/
  // Time: O(N)
  // Space: O(N)
  class Solution {
  public:
      int maxLevelSum(TreeNode* root) {
          if (!root) return 0;
          int maxSum = 0, ans = 0, lv = 1;
          queue<TreeNode*> q;
          q.push(root);
          while (q.size()) {
              int cnt = q.size(), sum = 0;
              while (cnt--) {
                  auto node = q.front();
                  q.pop();
                  sum += node->val;
                  if (node->left) q.push(node->left);
                  if (node->right) q.push(node->right);
              }
              if (sum > maxSum) {
                  maxSum = sum;
                  ans = lv;
              }
              ++lv;
          }
          return ans;
      }
  };
  

• # 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
  
  ############
  
  # 1161. Maximum Level Sum of a Binary Tree
  # https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/
  
  # 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: TreeNode) -> int:
          level = res = 1
          mmax = float('-inf')
          q = collections.deque([root])
          
          while q:
              val = 0
              n = len(q)
              
              for _ in range(n):
                  node = q.popleft()
                  val += node.val
                  for leaf in (node.left, node.right):
                      if leaf:
                          q.append(leaf)
              
              if val > mmax:
                  res = level
                  mmax = val
  ​
              level += 1
          
          return res
  
  

All Problems

All Solutions