Example: 1 / \ 2 3 / \ / \ 4 5 6 7 / 8 Output ==> 2
Note: Assume that root is at level 0.
Queue
to traverse the tree level by level.
1. Declare the Queue
to store the nodes.
2. Declare four record keeping variables - current level
, max level
, current level sum
and maximum sum
. Initialize them to 0
.
3. Queue the root
.
4. Loop till the Queue
becomes empty.
5. Within the loop, dequeue a node.
6. If the current element is null
, compare the current level sum
with the maximum sum
and update the tracking variables accordingly.
7. Reset the current level sum
variable and increent the level. Insert null
into the Queue
if the Queue
is not empty.
8. If the current element
is not null
, add its data to current level sum
and insert left
and right
nodes into the queue.
9. At the end of the loop, return the level
with maximum sum
.
public int findMaxSumLevel(TreeNode root) { }
C
Java
Python