Задача: 515. Find Largest Value in Each Tree Row
Дан корень двоичного дерева, верните массив наибольших значений в каждой строке дерева (индексация с 0).
Пример:
Input: root = [1,3,2,5,3,null,9]
Output: [1,3,9]
👨💻 Алгоритм:
1⃣Если корень дерева равен null (пустое дерево), верните пустой список. Инициализируйте список ans для хранения результатов и очередь с корнем дерева для выполнения поиска в ширину (BFS).
2⃣Выполните BFS, пока очередь не пуста: инициализируйте currMax минимальным значением и сохраните длину очереди в currentLength. Повторите currentLength раз: удалите узел из очереди, обновите currMax, если значение узла больше. Для каждого дочернего узла, если он не равен null, добавьте его в очередь.
3⃣Добавьте currMax в ans. Верните ans.
😊 Решение:
from collections import deque
from typing import List, Optional
class Solution:
def largestValues(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
ans = []
queue = deque([root])
while queue:
current_length = len(queue)
curr_max = float("-inf")
for _ in range(current_length):
node = queue.popleft()
curr_max = max(curr_max, node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
ans.append(curr_max)
return ans
👉Новости 👉Платформа