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.
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.
1 2 3 4 5 6 7 8 910111213141516171819202122232425
# 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 = rightclassSolution:defmaxLevelSum(self,root:Optional[TreeNode])->int:q=deque([root])mx=-infi=0whileq:i+=1s=0for_inrange(len(q)):node=q.popleft()s+=node.valifnode.left:q.append(node.left)ifnode.right:q.append(node.right)ifmx<s:mx=sans=ireturnans
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcmaxLevelSum(root*TreeNode)int{q:=[]*TreeNode{root}mx:=-0x3f3f3f3fi:=0ans:=0forlen(q)>0{i++s:=0forn:=len(q);n>0;n--{root=q[0]q=q[1:]s+=root.Valifroot.Left!=nil{q=append(q,root.Left)}ifroot.Right!=nil{q=append(q,root.Right)}}ifmx<s{mx=sans=i}}returnans}
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.
1 2 3 4 5 6 7 8 9101112131415161718192021
# 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 = rightclassSolution:defmaxLevelSum(self,root:Optional[TreeNode])->int:defdfs(node,i):ifnodeisNone:returnifi==len(s):s.append(node.val)else:s[i]+=node.valdfs(node.left,i+1)dfs(node.right,i+1)s=[]dfs(root,0)returns.index(max(s))+1
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcmaxLevelSum(root*TreeNode)int{s:=[]int{}vardfsfunc(*TreeNode,int)dfs=func(root*TreeNode,iint){ifroot==nil{return}iflen(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,-0x3f3f3f3ffori,v:=ranges{ifmx<v{mx=vans=i+1}}returnans}