Altura de un árbol binario
Tiempo máximo: 1,000 sMemoria máxima: 4096 KiB
La altura de un árbol binario se define recursivamente de la siguiente manera:
- si el árbol es vacío su altura es 0; y
- si el árbol no es vacío su altura es 1 más que el máximo de las alturas de sus hijos.
De los siguientes árboles, el de la izquierda tiene altura 3 y el de la derecha tiene altura 4.
Dado un árbol binario, ¿sabrías calcular su altura?
Entrada
La entrada comienza indicando el número de casos de prueba que vendrán a continuación. Cada caso consiste en una cadena de caracteres con la descripción de un árbol binario: el árbol vacío se representa con un punto (.); un árbol no vacío se representa con un * (que denota la raíz), seguido primero de la descripción del hijo izquierdo y después de la descripción del hijo derecho. Los árboles nunca contendrán más de 5.000 nodos.
Salida
Para cada árbol, se escribirá una línea con su altura.
Entrada de ejemplo
2 ***..*..*.. **..**..**..*..
Salida de ejemplo
3 4