Сложность: medium
Дано корневое дерево, уровень корня которого равен 1, уровень его детей равен 2 и так далее.
Верните наименьший уровень x, такой что сумма всех значений узлов на уровне x максимальна.
Пример:
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.
👨💻 Алгоритм:
1⃣Создайте целочисленную переменную maxSum для отслеживания максимальной суммы значений узлов на любом уровне, начав с большого отрицательного значения. Создайте переменную ans для хранения ответа на задачу. Создайте переменную level для хранения текущего уровня, через который мы проходим, и инициализируйте её значением 0. Инициализируйте очередь q типа TreeNode и добавьте в неё корень.
2⃣Выполните обход в ширину (BFS) до тех пор, пока очередь не станет пустой: увеличьте level на 1 и инициализируйте sumAtCurrentLevel = 0 для вычисления суммы всех значений узлов на этом уровне. Проходите через все узлы на уровне, используя только q.size() количество узлов. Внутри этого внутреннего цикла извлекайте все узлы на текущем уровне один за другим, добавляя их значения к sumAtCurrentLevel и добавляя левых и правых детей (если они существуют) в очередь. Поймите, что после прохождения всех узлов на уровне в очереди остаются только узлы уровня +1.
3⃣После прохождения всех узлов на уровне проверьте, больше ли sumAtCurrentLevel, чем maxSum. Если maxSum < sumAtCurrentLevel, обновите переменную ответа на ans = level и установите maxSum = sumAtCurrentLevel. Верните ans.
😎 Решение:
from collections import deque
class Solution:
def maxLevelSum(self, root: Optional[TreeNode]) -> int:
maxSum = float('-inf')
ans = 0
level = 0
q = deque([root])
while q:
level += 1
sumAtCurrentLevel = 0
for _ in range(len(q)):
node = q.popleft()
sumAtCurrentLevel += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
if maxSum < sumAtCurrentLevel:
maxSum = sumAtCurrentLevel
ans = level
return ans
Ставь 👍 и забирай 📚 Базу знаний