Problem Statement:
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.
Approach
This was a problem which had some quite interesting solving... In this approach I used a BFS. I took one row at a time found its sum and compared it with the previous sum. If its greater than the previous one then I replaced the max Level with the current Level. Finally at the end of the looping I returned the max Level.
Algo Images
Code
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:
if root == None: return None
currentLevel: int = 1
maxLevel: int = None
maxSum: int = None
BFSQueue: list[TreeNode] = [root]
while len(BFSQueue) > 0:
currentLength: int = len(BFSQueue)
currentSum: int = 0
for i in range(currentLength):
currentNode: TreeNode = BFSQueue.pop(0)
currentSum += currentNode.val
if currentNode.left != None: BFSQueue.append(currentNode.left)
if currentNode.right != None: BFSQueue.append(currentNode.right)
if (maxSum == None) or (maxSum < currentSum):
maxSum = currentSum
maxLevel = currentLevel
currentLevel += 1
return maxLevel
Result Image
If you got to learn something from this post make sure you like the post and click on the follow button for more such content.
Also if you have some suggestions and want to improve it make sure you comment down below...
Top comments (0)