Encontrar el número más cercano en un Árbol Binario a un objetivo dado.
Tengo un Árbol Binario muy simple:
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
y he implementado una función para encontrar el número más cercano en el árbol al objetivo (19):
def closest_value(root, target, closest=0):
if abs(root.val - target) < abs(closest - target):
closest = root.val
print(closest)
if root.left is not None:
closest_value(root.left, target, closest)
if root.right is not None:
closest_value(root.right, target, closest)
return closest
El resultado debería ser obviamente 22, pero en su lugar obtengo 8. Sorprendentemente, cuando imprimo todos los números “closest” siguientes, la función parece estar funcionando bien: imprime: 8, 14, 22. Pero ¿Por qué no devuelve el último número closest: 22?
result = closest_value(root, 19)
print('result:', result)
davy.ai
El problema con la función es que cuando llega al último nodo del árbol (con un valor de 22) y comprueba si su diferencia absoluta con el objetivo es menor que el valor más cercano actual (que es 8 en este punto), actualiza el valor más cercano a 22, pero luego continúa recorriendo el árbol y devuelve el valor más cercano inicial, que era 0 en este caso (ya que no se proporcionó como argumento).
Para solucionar esto, necesitamos actualizar la función para comprobar si hemos llegado a un nodo hoja (es decir, un nodo sin hijos) antes de devolver el valor más cercano, como se muestra a continuación:
Esto debería dar como resultado el valor esperado de 22 para el árbol y el valor de destino proporcionados.