Diameter of Binary Tree

+10

Se te da un árbol binario almacenado en el array tree en orden por niveles. La raíz está en el índice 0, los hijos del nodo en el índice i están en 2*i+1 (izquierda) y 2*i+2 (derecha), -1 marca una posición vacía y el array puede terminar con entradas -1 adicionales. Devuelve el diámetro del árbol: el número de aristas del camino más largo entre dos nodos cualesquiera. El camino puede pasar por la raíz o quedarse dentro de un subárbol.

Función

diameterOfBinaryTree(tree: integer-array) → integer

treeinteger-array: el árbol binario en orden por niveles, con -1 para una posición vacía
Devuelveinteger: el número de aristas en el camino más largo entre dos nodos

Restricciones

1 ≤ tree.length ≤ 32767
Cada tree[i] es -1 o un valor con 0 ≤ tree[i] ≤ 1000.
tree[0] nunca es -1, así que el árbol tiene al menos un nodo.
El array puede terminar con entradas -1 adicionales después del último nodo.
Ambos hijos de un espacio vacío también están vacíos, y la profundidad es como máximo 14.

Ejemplos

Entrada: tree = [8, 3, 6, 1, 4, -1, -1, -1, -1, 7]
Salida: 4
Explicación: La ruta 7, 4, 3, 8, 6 (índices 9, 4, 1, 0, 2) contiene cinco nodos unidos por cuatro aristas. Gira en la raíz: tres aristas hacia abajo por el lado izquierdo y una hacia abajo por el derecho.

Entrada: tree = [2, 5, -1, 1, 9, -1, -1, 3, -1, -1, 4]
Salida: 4
Explicación: El camino 3, 1, 5, 9, 4 tiene cuatro aristas y gira en el 5 en el índice 1. La raíz no tiene hijo derecho, así que un camino que pasa por la raíz solo tiene las tres aristas que bajan por su lado izquierdo.

Entrada: tree = [6, -1, -1]
Salida: 0
Explicación: Un nodo aislado no tiene aristas. El camino más largo es el propio nodo, de longitud 0.

+12 pruebas ocultas al enviar

Para ir más allá

¿Cómo devolverías la ruta en sí, los valores de los nodos desde un extremo del diámetro hasta el otro?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

La ruta más larga no tiene que pasar por la raíz, así que medir los dos lados de la raíz no es suficiente. Cada ruta tiene un nodo más alto, donde cambia de subir a bajar, y la ruta más larga que cambia de dirección en un nodo es la suma de su altura izquierda y su altura derecha. Una pasada en orden posterior calcula cada altura de abajo hacia arriba y comprueba cada punto de cambio en el camino, en O(n).

Mide cada par de nodos

Correcto, pero no termina con las pruebas más grandes

Intuición

Primero, cómo moverse por el arreglo. El nodo en el índice i tiene su hijo izquierdo en 2*i+1 y su hijo derecho en 2*i+2, así que su padre se encuentra en (i-1)/2, redondeado hacia abajo. Una posición existe solo si su índice está dentro del arreglo y el valor que contiene no es -1. En [8, 3, 6, 1, 4, -1, -1, -1, -1, 7], el 7 en el índice 9 tiene su padre en el índice 4, y ese 4 tiene su padre en el índice 1.

El diámetro es la mayor distancia entre dos nodos, así que puedes medir cada par. Para obtener la distancia entre los índices a y b, avanza hacia la raíz un paso a la vez hasta que se encuentren, siempre desde el índice mayor. Un índice mayor nunca está en un nivel más alto, así que ese paso nunca pasa del punto de encuentro. El número de pasos es el número de aristas. Para 9 y 2: el 9 sube a 4 y después a 1, el 2 sube a 0, y el 1 sube a 0. Cuatro pasos.

Esto es correcto, pero lento. La prueba más grande es un árbol completo de 16383 nodos, lo que genera alrededor de 1.3 × 10^8 pares, y cada par requiere hasta 26 pasos. Miles de millones de pasos para una sola respuesta superan por mucho el límite de tiempo.

Algoritmo

Recopila los índices de todos los nodos reales.
Para cada par (a, b), establece edges = 0 y repite hasta que a == b: reemplaza el índice mayor por su padre y suma 1 a edges.
Conserva el valor más grande de edges que veas y devuélvelo.

def diameterOfBinaryTree(tree):
    nodes = [i for i, value in enumerate(tree) if value != -1]
    best = 0
    for x in range(len(nodes)):
        for y in range(x + 1, len(nodes)):
            a, b = nodes[x], nodes[y]
            edges = 0
            while a != b:
                # A larger index is never higher up, so climb from it.
                if a > b:
                    a = (a - 1) // 2
                else:
                    b = (b - 1) // 2
                edges += 1
            best = max(best, edges)
    return best

Mide ambas alturas en cada nodo

Intuición

Observa el camino más largo desde su nodo más alto, el nodo donde deja de subir y empieza a bajar. Desde allí, baja todo lo posible por el lado izquierdo y todo lo posible por el lado derecho. Sea height(c) el número de nodos del camino descendente más largo desde c, con 0 para una posición vacía. Entonces, el camino más largo que gira en el nodo i tiene height(2*i+1) + height(2*i+2) aristas, una arista por cada uno de esos nodos.

Así que prueba cada nodo como punto de giro y conserva el mejor resultado. En el segundo ejemplo, el 5 en el índice 1 tiene altura 2 a la izquierda (1, 3) y 2 a la derecha (9, 4), lo que da un camino de cuatro aristas. La raíz tiene altura 3 a la izquierda y 0 a la derecha, lo que da solo tres.

Cada llamada a height recorre un subárbol completo, y se vuelve a recorrer un nodo por cada antecesor que tiene encima, así que el trabajo es O(n·h). Como h ≤ 14, es suficientemente rápido en este caso, pero en un árbol de punteros con forma de cadena, h puede llegar a n y la misma idea cuesta O(n²). Las llamadas repetidas a height son el trabajo innecesario que elimina el último enfoque.

Algoritmo

Escribe height(i): 0 para una posición vacía; en caso contrario, 1 + max(height(2*i+1), height(2*i+2)).
Para cada nodo real i, calcula height(2*i+1) + height(2*i+2).
Devuelve la mayor de estas sumas.

def diameterOfBinaryTree(tree):
    n = len(tree)

    def height(i):
        # Nodes on the longest downward path from i; an empty spot has 0.
        if i >= n or tree[i] == -1:
            return 0
        return 1 + max(height(2 * i + 1), height(2 * i + 2))

    best = 0
    for i in range(n):
        if tree[i] != -1:
            # The longest path that turns at node i goes down both sides.
            best = max(best, height(2 * i + 1) + height(2 * i + 2))
    return best

Una pasada en postorden por las alturas

Intuición

La altura de un nodo depende únicamente de las alturas de sus dos hijos, que son los mismos dos números que necesita la comprobación del punto de giro. Así que calcúlalas una sola vez, de abajo hacia arriba. Un recorrido en postorden termina de procesar ambos hijos antes que su padre. En cada nodo, entonces tienes left y right: actualiza la respuesta con left + right y pasa 1 + max(left, right) al padre.

En el primer ejemplo, la hoja 7 devuelve 1, el 4 que está encima devuelve 2 y el 3 devuelve 3, ya que su otro hijo, 1, tiene una altura de 1. El 6 devuelve 1. En la raíz, left + right = 3 + 1 = 4, que es la respuesta. Lo mejor que ofrece cualquier otro nodo es el 3, con 1 + 2 = 3.

Se visita cada nodo una vez, así que el tiempo es O(n), y la recursión alcanza una profundidad igual a la del árbol, O(h), aproximadamente un marco por nivel. La respuesta se guarda en una variable fuera de la recursión, porque lo que devuelve una llamada (una altura) no es lo que quieres al final (la longitud de un camino).

Algoritmo

Establece best = 0 y escribe height(i). Para una posición vacía, devuelve 0.
Calcula left = height(2*i+1) y right = height(2*i+2).
Establece best como el mayor entre best y left + right.
Devuelve 1 + max(left, right).
Llama a height(0) y devuelve best.

def diameterOfBinaryTree(tree):
    n = len(tree)
    best = 0

    def height(i):
        # Returns the height of node i and updates best on the way back up.
        nonlocal best
        if i >= n or tree[i] == -1:
            return 0
        left = height(2 * i + 1)
        right = height(2 * i + 2)
        best = max(best, left + right)  # the longest path that turns at node i
        return 1 + max(left, right)

    height(0)
    return best

Errores comunes y casos límite

La mayoría de las respuestas incorrectas cuentan lo que no corresponde o miden en el nodo equivocado.

Contar nodos en lugar de aristas. El camino 7, 4, 3, 8, 6 tiene cinco nodos y una longitud de 4, y un solo nodo tiene un diámetro de 0.
Medir solo pasando por la raíz. En el segundo ejemplo, el mejor camino que pasa por la raíz tiene tres aristas, y la respuesta es cuatro, con el giro en el índice 1.
Devolver el diámetro desde la llamada recursiva. El padre necesita las alturas de sus hijos para construir caminos más largos; el diámetro debe guardarse en una variable aparte.
Mezclar dos convenciones de altura. Con alturas que cuentan nodos y 0 para una posición vacía, left + right ya es el número de aristas. Las alturas que cuentan aristas necesitan -1 para una posición vacía y left + right + 2. Usar la mitad de una convención y la mitad de la otra da un resultado desfasado por uno o dos.
Leer más allá del final. Una hoja cerca del final del arreglo puede tener índices de hijos que superen su última posición. Trata un índice que supera el final como una posición vacía.
Confundir el desplazamiento en Lua y R, donde los arreglos empiezan en 1. Mantén los índices de los nodos basados en 0 para la operación 2*i+1 y lee tree[i + 1].

Preguntas frecuentes4

¿Cuál es la complejidad temporal del diámetro de un árbol binario?

La solución en postorden visita cada nodo una vez, así que se ejecuta en tiempo O(n) y usa O(h) de espacio adicional para la recursión, donde h es la altura. Calcular las alturas por separado en cada nodo cuesta O(n·h), lo que se convierte en O(n²) en un árbol con forma de cadena.

¿El diámetro de un árbol binario siempre pasa por la raíz?

No. El camino más largo puede estar completamente dentro de un subárbol, por ejemplo, cuando la raíz tiene una rama corta y un subárbol profundo y frondoso al otro lado. Por eso compruebas left + right en cada nodo, no solo en la raíz.

¿El diámetro se cuenta en nodos o en aristas?

Aquí se cuenta en aristas, los enlaces entre nodos consecutivos de la ruta, así que un solo nodo tiene diámetro 0 y dos nodos conectados tienen diámetro 1. Algunos libros cuentan nodos en su lugar, lo que da uno más. Comprueba cuál pide el problema antes de sumar o restar 1.

¿Cómo se encuentra el diámetro de un árbol binario sin recursión?

Visita los nodos en un orden en el que cada hijo aparezca antes que su padre. Una forma: coloca la raíz en una pila, saca nodos y añádelos a una lista mientras colocas sus hijos en la pila; después recorre esa lista hacia atrás. Guarda la altura de cada nodo en un array, lee las alturas de los dos hijos en cada nodo y actualiza la respuesta con su suma. El tiempo sigue siendo O(n).

Python

def diameterOfBinaryTree(tree):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

tree = [8, 3, 6, 1, 4, -1, -1, -1, -1, 7]

Esperado

Diameter of Binary Tree

Función

Restricciones

Ejemplos

Pistas

Solución

Mide cada par de nodos

Mide ambas alturas en cada nodo

Una pasada en postorden por las alturas

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares