Является ли двоичное дерево полным?
Является ли заданное двоичное дерево полным? Полное двоичное дерево — это особый вид двоичного дерева, в котором каждый узел либо имеет двух потомков, либо не имеет ни одного. Такое дерево также называют proper двоичным деревом.
Входные данные
Входные данные содержат целые числа, разделённые пробелами, которые представляют значения в узлах двоичного дерева. Порядок значений задан так, как описано в предыдущем объяснении (при каждом обходе сначала переходим к левому, затем к правому поддереву). Значение 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 |
Пояснения
В первом примере двоичное дерево является полным, так как у всех узлов либо нет потомков, либо их два.
Во втором примере дерево не является полным, так как у узла со значением 3 только один потомок.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB