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 use BFS to traverse level by level, calculating 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 number.
Specifically, we use a queue q to store the nodes of the current level. During each traversal, we record the sum of nodes at the current level as s, then add all child nodes of the current level to the queue to prepare for the next level. We use variable mx to record the current maximum sum, and variable ans to record the corresponding level number. After calculating the sum of each level, if s is greater than mx, we update mx and ans. Finally, we return ans.
The time complexity is O(n) and the space complexity is O(n), where n is the number of nodes in the binary tree.
PythonJavaC++GoTypeScriptRust
# 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(code-box)
/**
* 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;
}
}(code-box)
/**
* 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;
}
};(code-box)
/**
* 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
}(code-box)
/**
* 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 {
let q = [root];
let i = 0;
let mx = -Infinity;
let ans = 0;
while (q.length) {
++i;
const nq = [];
let s = 0;
for (const { val, left, right } of q) {
s += val;
left && nq.push(left);
right && nq.push(right);
}
if (mx < s) {
mx = s;
ans = i;
}
q = nq;
}
return ans;
}(code-box)
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
use std::collections::VecDeque;
impl Solution {
pub fn max_level_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
let mut q = VecDeque::new();
if let Some(r) = root {
q.push_back(r);
}
let mut i = 0;
let mut mx = i32::MIN;
let mut ans = 0;
while !q.is_empty() {
i += 1;
let mut s = 0;
let sz = q.len();
for _ in 0..sz {
let node = q.pop_front().unwrap();
let node = node.borrow();
s += node.val;
if let Some(left) = node.left.clone() {
q.push_back(left);
}
if let Some(right) = node.right.clone() {
q.push_back(right);
}
}
if s > mx {
mx = s;
ans = i;
}
}
ans
}
}(code-box)
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.
PythonJavaC++Go
# 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(code-box)
/**
* 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);
}
}(code-box)
/**
* 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);
}
};(code-box)
/**
* 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
}(code-box)
