Сложность: medium
Дан корень бинарного дерева, определите, является ли оно полным бинарным деревом.
В полном бинарном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. На последнем уровне h может быть от 1 до 2^h узлов включительно.
Пример:
Input: root = [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.
👨💻 Алгоритм:
1⃣Если корень дерева равен null, верните true.
2⃣Инициализируйте переменную nullNodeFound как false для отслеживания того, встречался ли уже null-узел. Создайте очередь и поместите в неё корень дерева.
3⃣Пока очередь не пуста:
Извлеките первый элемент из очереди.
Если элемент равен null, установите nullNodeFound в true.
Если элемент не равен null, проверьте, встречался ли уже null-узел. Если nullNodeFound равен true, верните false. В противном случае добавьте в очередь левого и правого потомков текущего узла.
😎 Решение:
from collections import deque
class Solution:
def isCompleteTree(self, root: TreeNode) -> bool:
if not root:
return True
queue = deque([root])
nullNodeFound = False
while queue:
node = queue.popleft()
if not node:
nullNodeFound = True
else:
if nullNodeFound:
return False
queue.append(node.left)
queue.append(node.right)
return True
Ставь 👍 и забирай 📚 Базу знаний