Encuentra la cantidad de nodos que tienen un solo nodo hijo
La construcción de un árbol binario se puede realizar de forma recursiva. Supongamos que el árbol se construye a partir de la entrada del usuario. Si el nodo no existe, el usuario ingresa 0, y si sí existe, se ingresa un número positivo.
Comenzando desde la raíz, se lee la entrada del usuario y se continúa hacia la subrama correspondiente si el número es positivo, deteniendo la construcción recursiva en esa rama si el valor es 0.
vals = map(int, input().split()) # Lee los valores de BST de la entrada
idx = 0 # El índice del valor actual
root = Node(vals[idx]) # Establece el valor del nodo raíz
def read(node: Node): # Lee recursivamente todos los datos del árbol
if node.value == 0: # Si el valor actual es 0 => el nodo no existe
return # No se leen sus nodos izquierdo y derecho
node.left = Node(vals[idx + 1]) # Establece el valor del nodo izquierdo
node.right = Node(vals[idx + 2]) # Establece el valor del nodo derecho
idx += 2 # Actualiza el índice del valor actual
read(node.left) # Pide al usuario datos del subárbol izquierdo
read(node.right) # Pide al usuario datos del subárbol derechoAquí puede observarse que la cantidad de nodos no está determinada inicialmente. El programa lee de forma recursiva toda la entrada, comenzando por la parte izquierda y continuando hasta que el valor del nodo sea 0. Luego sigue con la parte derecha y así sucesivamente. Este proceso continúa hasta que todos los nodos inferiores se establecen a 0 y no quedan más datos por leer. Para el árbol representado en la imagen, la entrada del usuario podría ser la siguiente:
1 # root
2 # root.left
3 # root.right
4 # root.left.left
5 # root.left.right
0 # root.left.left.left does not exist
0 # root.left.left.right does not exist
0 # root.left.right.left does not exist
0 # root.left.right.right does not exist
6 # root.right.left
7 # root.right.right
0 # root.right.left.left does not exist
0 # root.right.left.right does not exist
8 # root.right.right.left
9 # root.right.right.right
0 # root.right.right.left.left does not exist
0 # root.right.right.left.right does not exist
0 # root.right.right.right.left does not exist
0 # root.right.right.right.right does not existEsta entrada también puede representarse como un arreglo:
[1, 2, 3, 4, 5, 0, 0, 0, 0, 6, 7, 0, 0, 8, 9, 0, 0, 0, 0], que describe el mismo árbol binario. En lugar de solicitar al usuario un número cada vez, podríamos iterar sobre este arreglo y construir el árbol de manera recursiva de la misma forma descrita anteriormente.Dado un árbol binario válido, se pide calcular la cantidad de nodos que tienen exactamente un solo nodo hijo.
Entrada
La entrada contiene enteros separados por espacios que representan los valores de los nodos del árbol binario. El orden de los valores es el descrito anteriormente. Un valor de 0 indica que el nodo no existe.
Salida
El programa debe imprimir la cantidad de nodos en un árbol binario que tienen un solo hijo.
Ejemplos
Entrada | Salida |
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 |
Explicación
- En el primer ejemplo, el árbol binario no tiene ningún nodo con un solo hijo.
- En el segundo ejemplo, el árbol binario solo cuenta con un nodo que tiene un solo hijo, el nodo con el número 3.
Pro tip 😎
Puedes modificar el código anterior para crear los nodos de forma condicional: solo se crea un nodo y se asigna a
node.left o node.right si el valor ingresado es distinto de 0.Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB