Problema número 275

¿Está el árbol equilibrado?

Tiempo máximo: 1,000-2,000 sMemoria máxima: 4096 KiB

Un árbol binario está equilibrado si bien es vacío o bien cumple que la diferencia de alturas de sus dos hijos es como mucho 1 y además ambos están equilibrados.

De los siguientes árboles los dos primeros están equilibrados, pero el tercero no lo está.

Tres árboles binarios, los dos primeros equilibrados

Dado un árbol binario, queremos averiguar si está equilibrado o no.

Entrada

La entrada comienza con el número de casos que vienen a continuación. Cada caso de prueba consiste en una línea 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 una R (que denota la raíz) seguida de la descripción del hijo izquierdo y del hijo derecho. Los árboles nunca contendrán más de 5.000 nodos.

Salida

Para cada árbol, se escribirá en una línea SI si el árbol está equilibrado y NO si no lo está.

Entrada de ejemplo

3
RRR..R..R.R..
RR.R..RR..R.R..
RR..RR..R.R..

Salida de ejemplo

SI
SI
NO