Является ли двоичное дерево полным?
Является ли заданное двоичное дерево полным? Полное двоичное дерево — это особый вид двоичного дерева, в котором каждый узел либо имеет двух потомков, либо не имеет ни одного. Такое дерево также называют proper двоичным деревом.
.png?table=block&id=18a2c681-664d-8154-bd91-eb0e4ede93eb&cache=v2)
Входные данные
Входные данные содержат целые числа, разделённые пробелами, которые представляют значения в узлах двоичного дерева. Порядок значений задан так, как описано в предыдущем объяснении (при каждом обходе сначала переходим к левому, затем к правому поддереву). Значение 0 означает, что узел отсутствует. Гарантируется, что входные данные задают корректное двоичное дерево.
Выходные данные
Программа должна вывести
Yes, если двоичное дерево является полным, и No в противном случае.Примеры
Вход | Выход |
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0 | Yes |
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0 | No |
Пояснения
- В первом примере двоичное дерево является полным, так как у всех узлов либо нет потомков, либо их два.
.png?table=block&id=18a2c681-664d-81bd-afea-f071c3b179ed&cache=v2)
- Во втором примере дерево не является полным, так как у узла со значением 3 только один потомок.
.png?table=block&id=18a2c681-664d-81e4-9201-dd738af4b10c&cache=v2)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB