Является ли двоичное дерево полным?
Вам нужно определить, является ли данное двоичное дерево полным.
Двоичное дерево считается полным, если все его уровни полностью заполнены, за исключением нижнего, при этом узлы на нижнем уровне располагаются как можно левее.
Оба дерева, представленные ниже, являются примерами полных двоичных деревьев.
Ввод
Во входных данных даются целые числа, разделенные пробелами, которые соответствуют значениям узлов двоичного дерева. Порядок значений задан так, как было описано в предыдущем пункте (каждый раз для обхода сначала берется левое поддерево, а затем правое). Значение 0 означает, что узел не существует. Гарантируется, что входное двоичное дерево корректно.
Вывод
Программа должна вывести
Yes, если двоичное дерево является полным, и No — в противном случае.Примеры
Input | Output |
1 2 3 4 5 8 9 0 0 0 0 0 0 6 7 0 0 0 0 | Yes |
1 2 3 4 5 8 0 0 0 0 0 6 7 0 0 0 0 | Yes |
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0 | No |
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0 | No |
Пояснение
- Пример 1 — это полное двоичное дерево, так как последний уровень заполнен слева.
- Пример 2 — это полное двоичное дерево, так как последний уровень заполнен слева.
- Пример 3 не является полным двоичным деревом, так как оно не заполнено максимально слева.
.png?table=block&id=18a2c681-664d-8144-bebe-e60c2fb87a15&cache=v2)
- Пример 4 не является полным двоичным деревом, так как оно не заполнено максимально слева.
.png?table=block&id=18a2c681-664d-818a-916a-effe537bd2f4&cache=v2)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB