Найдите количество узлов, у которых только один дочерний узел
Построение двоичного (бинарного) дерева может выполняться рекурсивно. Предположим, что дерево формируется на основании пользовательского ввода. Если узел не существует, пользователь вводит 0, а если узел существует, вводится положительное число.
Начиная от корня, мы считываем пользовательский ввод и переходим к ветви левого или правого поддерева, если значение положительное. Если встречаем 0, на этом месте ветвь отсутствует и рекурсия по этому направлению завершается.
vals = map(int, input().split()) # Считывает значения BST из входного потока
idx = 0 # Текущий индекс значения
root = Node(vals[idx]) # Присваивает значение корневому узлу
def read(node: Node): # Рекурсивно считывает все данные дерева
if node.value == 0: # Если текущее значение 0 => узел не существует
return # Поэтому не читаем его левого и правого потомков
node.left = Node(vals[idx + 1]) # Присваивает значение левому узлу
node.right = Node(vals[idx + 2]) # Присваивает значение правому узлу
idx += 2 # Обновляет текущий индекс
read(node.left) # Запрашиваем данные для левого поддерева
read(node.right) # Запрашиваем данные для правого поддереваЗдесь можно заметить, что изначально количество узлов не задаётся явно. Программа рекурсивно считывает все входные данные, начиная с левого поддерева, и продолжает эту процедуру до тех пор, пока значение узла не будет равно 0. После этого она переходит к чтению значений для правого поддерева. Такая схема продолжается, пока все нижние узлы не будут установлены в 0 и не останется чисел для чтения. Таким образом, для дерева, изображённого выше, пользователь мог ввести примерно следующие значения:
1 # root
2 # root.left
3 # root.right
4 # root.left.left
5 # root.left.right
0 # root.left.left.left не существует
0 # root.left.left.right не существует
0 # root.left.right.left не существует
0 # root.left.right.right не существует
6 # root.right.left
7 # root.right.right
0 # root.right.left.left не существует
0 # root.right.left.right не существует
8 # root.right.right.left
9 # root.right.right.right
0 # root.right.right.left.left не существует
0 # root.right.right.left.right не существует
0 # root.right.right.right.left не существует
0 # root.right.right.right.right не существуетДанный ввод можно представить и в виде массива:
[1, 2, 3, 4, 5, 0, 0, 0, 0, 6, 7, 0, 0, 8, 9, 0, 0, 0, 0], который описывает двоичное дерево. Вместо того чтобы на каждом шаге отдельно запрашивать входные данные, можно просто итерироваться по этому массиву и строить дерево рекурсивно точно таким же способом.Допустим, у нас есть корректное двоичное дерево. Требуется вычислить, сколько в нём узлов, у которых только один дочерний узел.
Ввод
Во входных данных даны целые числа, разделённые пробелами, обозначающие значения узлов двоичного дерева. Порядок значений дан, как описано выше. Число 0 означает, что узел не существует.
Вывод
Программа должна вывести количество узлов в двоичном дереве, у которых только один потомок.
Примеры
Ввод | Вывод |
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0 | 0 |
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0 | 1 |
Пояснение
- В первом примере в двоичном дереве нет узлов с одним потомком
- Во втором примере имеется ровно один узел с одним потомком – это узел со значением 3.
Pro tip 😎
Можно изменить код выше так, чтобы создавать узлы условно — то есть создавать и присваивать
node.left или node.right только в том случае, если считанное значение отлично от 0.Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB