Question

1161. Maximum Level Sum of a Binary Tree

中文文档

Description

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

Example 2:

Input: root = [989,null,10250,98693,-89388,null,null,null,-32127]
Output: 2

Constraints:

• The number of nodes in the tree is in the range [1, 104] .
• -105 <= Node.val <= 105

Solutions

Solution 1: BFS

We can use BFS to traverse the tree level by level, calculate the sum of nodes at each level, and find the level with the maximum sum. If there are multiple levels with the maximum sum, return the smallest level.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the 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: 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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode() {}
 *   TreeNode(int val) { this.val = val; }
 *   TreeNode(int val, TreeNode left, TreeNode right) {
 *     this.val = val;
 *     this.left = left;
 *     this.right = right;
 *   }
 * }
 */
class Solution {
  public int maxLevelSum(TreeNode root) {
    Deque<TreeNode> q = new ArrayDeque<>();
    q.offer(root);
    int mx = Integer.MIN_VALUE;
    int i = 0;
    int ans = 0;
    while (!q.isEmpty()) {
      ++i;
      int s = 0;
      for (int n = q.size(); n > 0; --n) {
        TreeNode node = q.pollFirst();
        s += node.val;
        if (node.left != null) {
          q.offer(node.left);
        }
        if (node.right != null) {
          q.offer(node.right);
        }
      }
      if (mx < s) {
        mx = s;
        ans = i;
      }
    }
    return ans;
  }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *   TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  int maxLevelSum(TreeNode* root) {
    queue<TreeNode*> q{{root}};
    int mx = INT_MIN;
    int ans = 0;
    int i = 0;
    while (!q.empty()) {
      ++i;
      int s = 0;
      for (int n = q.size(); n; --n) {
        root = q.front();
        q.pop();
        s += root->val;
        if (root->left) q.push(root->left);
        if (root->right) q.push(root->right);
      }
      if (mx < s) mx = s, ans = i;
    }
    return ans;
  }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */
func maxLevelSum(root *TreeNode) int {
  q := []*TreeNode{root}
  mx := -0x3f3f3f3f
  i := 0
  ans := 0
  for len(q) > 0 {
    i++
    s := 0
    for n := len(q); n > 0; n-- {
      root = q[0]
      q = q[1:]
      s += root.Val
      if root.Left != nil {
        q = append(q, root.Left)
      }
      if root.Right != nil {
        q = append(q, root.Right)
      }
    }
    if mx < s {
      mx = s
      ans = i
    }
  }
  return ans
}

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *   val: number
 *   left: TreeNode | null
 *   right: TreeNode | null
 *   constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 *   }
 * }
 */

function maxLevelSum(root: TreeNode | null): number {
  const queue = [root];
  let res = 1;
  let max = -Infinity;
  let h = 1;
  while (queue.length !== 0) {
    const n = queue.length;
    let sum = 0;
    for (let i = 0; i < n; i++) {
      const { val, left, right } = queue.shift();
      sum += val;
      left && queue.push(left);
      right && queue.push(right);
    }
    if (sum > max) {
      max = sum;
      res = h;
    }
    h++;
  }
  return res;
}

Solution 2: DFS

We can also use DFS to solve this problem. We use an array $s$ to store the sum of nodes at each level. The index of the array represents the level, and the value of the array represents the sum of nodes. We use DFS to traverse the binary tree, adding the value of each node to the sum of nodes at the corresponding level. Finally, we return the index corresponding to the maximum value in $s$.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the 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: Optional[TreeNode]) -> int:
    def dfs(node, i):
      if node is None:
        return
      if i == len(s):
        s.append(node.val)
      else:
        s[i] += node.val
      dfs(node.left, i + 1)
      dfs(node.right, i + 1)

    s = []
    dfs(root, 0)
    return s.index(max(s)) + 1

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode() {}
 *   TreeNode(int val) { this.val = val; }
 *   TreeNode(int val, TreeNode left, TreeNode right) {
 *     this.val = val;
 *     this.left = left;
 *     this.right = right;
 *   }
 * }
 */
class Solution {
  private List<Integer> s = new ArrayList<>();

  public int maxLevelSum(TreeNode root) {
    dfs(root, 0);
    int mx = Integer.MIN_VALUE;
    int ans = 0;
    for (int i = 0; i < s.size(); ++i) {
      if (mx < s.get(i)) {
        mx = s.get(i);
        ans = i + 1;
      }
    }
    return ans;
  }

  private void dfs(TreeNode root, int i) {
    if (root == null) {
      return;
    }
    if (i == s.size()) {
      s.add(root.val);
    } else {
      s.set(i, s.get(i) + root.val);
    }
    dfs(root.left, i + 1);
    dfs(root.right, i + 1);
  }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *   TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  int maxLevelSum(TreeNode* root) {
    vector<int> s;
    dfs(root, 0, s);
    int mx = INT_MIN;
    int ans = 0;
    for (int i = 0; i < s.size(); ++i)
      if (mx < s[i]) mx = s[i], ans = i + 1;
    return ans;
  }

  void dfs(TreeNode* root, int i, vector<int>& s) {
    if (!root) return;
    if (s.size() == i)
      s.push_back(root->val);
    else
      s[i] += root->val;
    dfs(root->left, i + 1, s);
    dfs(root->right, i + 1, s);
  }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */
func maxLevelSum(root *TreeNode) int {
  s := []int{}
  var dfs func(*TreeNode, int)
  dfs = func(root *TreeNode, i int) {
    if root == nil {
      return
    }
    if len(s) == i {
      s = append(s, root.Val)
    } else {
      s[i] += root.Val
    }
    dfs(root.Left, i+1)
    dfs(root.Right, i+1)
  }
  dfs(root, 0)
  ans, mx := 0, -0x3f3f3f3f
  for i, v := range s {
    if mx < v {
      mx = v
      ans = i + 1
    }
  }
  return ans
}