Un árbol binario está balanceado en altura si, en cada nodo, las alturas de su subárbol izquierdo y de su subárbol derecho difieren en a lo más \(1\) (la altura de un árbol vacío es \(0\)). Di si el árbol dado está balanceado.

Entrada

El árbol viene en el formato de LeetCode, en dos líneas: la primera tiene un entero \(k\) y la segunda \(k\) elementos separados por espacios, que son el recorrido por niveles del árbol. Cada elemento es el valor de un nodo o null si ese hijo no existe; los hijos de un null no se escriben y los null del final se omiten. Un árbol vacío se escribe con \(k = 0\) y una línea vacía.

El árbol tiene a lo más \(2 \cdot 10^4\) nodos y altura a lo más \(1000\); \(|v| \le 1000\).

Salida

true si el árbol está balanceado o false si no.

Ejemplo 1

Entrada

7
3 9 20 null null 15 7

Salida

true

Ejemplo 2

Entrada

9
1 2 2 3 3 null null 4 4

Salida

false

Ejemplo 3

Entrada

0

Salida

true

Basado en el problema 110 de LeetCode, Balanced Binary Tree, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.