Сложность: medium
Дано корень бинарного дерева, представьте, что вы стоите с правой стороны от него, верните значения узлов, которые вы видите, упорядоченные сверху вниз.
Пример:
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
👨💻 Алгоритм:
1️⃣Инициализируйте список правого обзора rightside. Инициализируйте две очереди: одну для текущего уровня и одну для следующего. Добавьте корень в очередь nextLevel.
2️⃣Пока очередь nextLevel не пуста: Инициализируйте текущий уровень: currLevel = nextLevel и очистите очередь следующего уровня nextLevel. Пока очередь текущего уровня не пуста: Извлеките узел из очереди текущего уровня. Добавьте сначала левый, а затем правый дочерний узел в очередь nextLevel. Теперь очередь currLevel пуста, и узел, который у нас есть, является последним и составляет часть правого обзора. Добавьте его в rightside.
3️⃣Верните rightside.
😎 Решение:
class Solution:
def rightSideView(self, root: TreeNode) -> List[int]:
if root is None:
return []
next_level = deque([root])
rightside = []
while next_level:
curr_level = next_level
next_level = deque()
while curr_level:
node = curr_level.popleft()
if node.left:
next_level.append(node.left)
if node.right:
next_level.append(node.right)
rightside.append(node.val)
return rightside
Ставь 👍 и забирай 📚 Базу знаний