Cómo sumar las profundidades de un árbol binario, ¿por qué mi código falla en las pruebas? – No estoy seguro de cómo configurar árboles binarios en mi IDE, así que no puedo usar el depurador.
Estoy resolviendo una pregunta donde se nos pide “devolver la suma de las profundidades” de todos los nodos en un “Árbol Binario”.
Por ejemplo:
aquí encontrarás una imágen de un árbol binario
Normalmente, usaría un “depurador” para encontrar el error en mi código, pero no sé cómo configurar “árboles/árbol binario en mi IDE”.
Mi código a continuación pasa la mayoría de las pruebas, pero falla en algunas. Falla en la prueba anterior y produce una “salida de 20” en lugar de “16”.
def nodeDepths(root):
queue = [root]
sumOfDepths = 0
currentDepth = 0
while len(queue):
for _ in range(len(queue)):
currentNode = queue.pop()
sumOfDepths += currentDepth
if currentNode.left:
queue.append(currentNode.left)
if currentNode.right:
queue.append(currentNode.right)
currentDepth += 1
return sumOfDepths
¿Alguna sugerencia de dónde falla el código/está haciendo algo inesperado?
davy.ai
El problema con el código es que está sumando la profundidad actual de cada nodo en la cola, lo cual es incorrecto. La profundidad de un nodo en un árbol es el número de aristas desde la raíz hasta ese nodo, no el número de nodos en el camino.
Para corregir el código, necesitamos agregar una variable que lleve un registro de la profundidad actual de cada nodo, y sumar eso a la suma de profundidades de cada nodo. Aquí hay una versión modificada del código que debería funcionar:
En esta versión del código, usamos una tupla para almacenar tanto el nodo actual como su profundidad en la cola. También actualizamos la profundidad actual para cada nodo hijo agregando 1 a la profundidad del padre. De esta manera, contamos la profundidad real de cada nodo en el árbol, en lugar de contar solo el número de nodos en el camino.