Verificamos exhaustivamente cada uno de los tutoriales de nuestra página web con la meta de enseñarte en todo momento información con la mayor veracidad y actualizada.
Solución:
Intentaré explicar cómo funciona este algoritmo recursivo:
height(10) = max(height(5), height(30)) + 1
height(30) = max(height(28), height(42)) + 1
height(42) = 0 (no children)
height(28) = 0 (no children)
height(5) = max(height(4), height(8)) + 1
height(4) = 0 (no children)
height(8) = 0 (no children)
Así que si quieres calcular height(10)
tiene que expandir la recursión hacia abajo y luego sustituir los resultados hacia atrás.
height(5) = max(0, 0) + 1
height(30) = max(0, 0) + 1
height(10) = max(1, 1) + 1
height(10) = 2
EDITAR:
Como se señala en los comentarios:height of binary tree = number of layers - 1
Por lo tanto, debe suponerse que la altura del nodo vacío es igual a -1, es decir:
height(empty) = -1
o
height(null) = -1
Por aquí
height(42) = max(height(null), height(null)) + 1
height(42) = max(-1, -1) + 1
height(42) = -1 + 1
height(42) = 0
He corregido el cálculo anterior.
La altura del árbol es la longitud del camino desde la raíz hasta el nodo más profundo del árbol. Aquí está el algoritmo más corto para hacerlo.
int height(Node root)
if(root == null )
return 0;
return 1+maxheight(root.left), height(root.right);
¿Conoces la definición de altura del nodo? Lo respondería como la distancia más lejana a una hoja alcanzable (por lo que todas las hojas tienen una altura de 0) … ahora intente encontrar la altura de cada nodo de abajo hacia arriba … ese sería su algoritmo …