Optimizar el diámetro del árbol binario en Python.

Me pregunto cómo puedo encontrar de manera óptima el diámetro (o la ruta más larga entre dos nodos de hoja) de un árbol binario. Tengo la solución básica a continuación, pero la segunda solución requiere pasar punteros. ¿Cómo puedo hacer algo como esto en Python?

def find_tree_diameter(node): if node == None: return 0 lheight = height(node.left) rheight = height(node.right) ldiameter = find_tree_diameter(node.left) rdiameter = find_tree_diameter(node.right) return max(lheight+rheight+1, ldiameter, rdiameter) def find_tree_diameter_optimized(node, height): lheight, rheight, ldiameter, rdiameter = 0, 0, 0, 0 if node == None: # *height = 0; return 0 ldiameter = diameterOpt(root.left, &lheight) rdiameter = diameterOpt(root.right, &rheight) # *height = max(lheight, rheight) + 1; return max(lh + rh + 1, max(ldiameter, rdiameter)); 

Python admite varios valores de retorno, por lo que no necesita argumentos de puntero como en C o C ++. Aquí hay una traducción del código:

 def diameter_height(node): if node is None: return 0, 0 ld, lh = diameter_height(node.left) rd, rh = diameter_height(node.right) return max(lh + rh + 1, ld, rd), 1 + max(lh, rh) def find_tree_diameter(node): d, _ = diameter_height(node) return d 

La función diameter_height altura devuelve el diámetro y la altura del árbol, y find_tree_diameter usa solo para calcular el diámetro (descartando la altura).

La función es O (n), sin importar la forma del árbol. La función original es O (n ^ 2) en el peor de los casos cuando el árbol está muy desequilibrado debido a los cálculos de altura repetidos.