Boundary Traversal of Binary Tree

Q: ¿Cuál es la complejidad temporal del recorrido del límite?

O(n) . Cada uno de los dos recorridos por los bordes sigue un camino, y el recorrido por las hojas visita cada nodo una vez. El espacio adicional es O(h) para la recursión o la pila.

MedioRecorrido de árboles

+10

El arreglo root contiene un árbol binario en orden por niveles: la raíz en el índice 0, los hijos del índice i en 2i+1 (izquierda) y 2i+2 (derecha), -1 para una posición vacía y posiblemente entradas -1 adicionales al final. Una hoja es un nodo sin hijos.

Devuelve el contorno en sentido antihorario desde la raíz:

La raíz.
El contorno izquierdo, de arriba abajo: desde el hijo izquierdo de la raíz, avanza al hijo izquierdo si lo hay; de lo contrario, al hijo derecho. Detente antes de una hoja.
Todas las hojas, de izquierda a derecha.
El contorno derecho, de abajo arriba: el reflejo del izquierdo, desde el hijo derecho de la raíz.

Ningún nodo se enumera dos veces, así que un árbol de un solo nodo contiene únicamente su raíz.

Función

boundaryTraversal(root: integer-array) → integer-array

rootinteger-array: el árbol binario en orden por niveles, con -1 para una posición vacía
Devuelveinteger-array: los valores límite, en sentido antihorario desde la raíz

Restricciones

1 ≤ root.length ≤ 32767
Cada root[i] es -1 o un valor con 0 ≤ root[i] ≤ 10⁵.
root[0] nunca es -1, así que el árbol tiene al menos un nodo.
El arreglo 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.
Los valores de los nodos son distintos.

Ejemplos

Entrada: root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]
Salida: [7, 3, 1, 4, 6, 8, 9]
Explicación: Después de la raíz 7, el límite izquierdo es 3: su hijo 1 es una hoja. Las hojas son 1, 4, 6, 8. El límite derecho es 9, por encima de la hoja 8.

Entrada: root = [10, 4, -1, -1, 6, -1, -1, -1, -1, 5, 8]
Salida: [10, 4, 6, 5, 8]
Explicación: 4 no tiene hijo izquierdo, así que el límite izquierdo pasa a 6 y después se detiene en la hoja 5. Las hojas 5, 8 vienen después. La raíz no tiene hijo derecho.

Para ir más allá

¿Cómo enumerarías el límite en sentido horario: la raíz, el borde derecho de arriba abajo, las hojas de derecha a izquierda y después el borde izquierdo de abajo arriba?

Pistas

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

0 de 3 abiertas

Solución

La respuesta une cuatro partes: la raíz, un recorrido hacia abajo por el borde izquierdo, las hojas de izquierda a derecha y un recorrido hacia abajo por el borde derecho leído al revés. En las uniones, una hoja que termina un borde y una raíz que es una hoja deben aparecer una sola vez cada una.

Recorre las tres partes por separado

Intuición

Cada borde corresponde a un camino: desde el hijo de la raíz, enumera los nodos hasta que el siguiente sería una hoja, que se enumera en la parte de las hojas. Un recorrido en preorden que va primero a la izquierda y luego a la derecha encuentra las hojas en orden de izquierda a derecha, porque todos los nodos de un subárbol izquierdo están a la izquierda del subárbol derecho, sin importar su profundidad. Recopila el borde derecho de arriba abajo y añádelo en orden inverso.

Los bordes siguen un camino cada uno y el recorrido de las hojas visita cada nodo una vez: tiempo O(n), con una recursión de h niveles de profundidad.

Algoritmo

Empieza por la raíz; si es una hoja, devuélvela.
Desde el índice 1, mientras el nodo exista y no sea una hoja, añádelo y pasa a su hijo izquierdo, o a su hijo derecho si no tiene uno izquierdo.
Recorre en preorden, primero por la izquierda, desde los índices 1 y 2, añadiendo todas las hojas.
Desde el índice 2, haz lo mismo que en el paso 2, dando preferencia a los hijos derechos, y recoge los nodos.
Añade los nodos recogidos en orden inverso.

def boundaryTraversal(root):
    n = len(root)

    def real(i):
        return i < n and root[i] != -1

    def is_leaf(i):
        return not real(2 * i + 1) and not real(2 * i + 2)

    result = [root[0]]
    if is_leaf(0):
        return result

    # 1. The left boundary, top-down, stopping before its leaf.
    i = 1
    while real(i) and not is_leaf(i):
        result.append(root[i])
        i = 2 * i + 1 if real(2 * i + 1) else 2 * i + 2

    # 2. Every leaf: a pre-order walk meets them from left to right.
    def add_leaves(i):
        if not real(i):
            return
        if is_leaf(i):
            result.append(root[i])
            return
        add_leaves(2 * i + 1)
        add_leaves(2 * i + 2)

    add_leaves(1)
    add_leaves(2)

    # 3. The right boundary, collected top-down and added bottom-up.
    right = []
    i = 2
    while real(i) and not is_leaf(i):
        right.append(root[i])
        i = 2 * i + 2 if real(2 * i + 2) else 2 * i + 1
    result.extend(reversed(right))
    return result

Un recorrido en preorden con indicadores de aristas

Intuición

Combina los recorridos en un único recorrido en preorden con una pila, asignando una marca a cada nodo: 1 en el borde izquierdo, 2 en el borde derecho y 0 en el interior. Los hijos de la raíz empiezan con 1 y 2. Un nodo del borde pasa su marca al hijo que está de su lado o a su único hijo; los demás hijos reciben 0. En el segundo ejemplo, la marca 1 pasa de 4 a 6 y luego a 5.

A medida que los nodos salen de la pila, agrega todas las hojas y todos los nodos que no sean hojas marcados con 1; reúne los nodos que no sean hojas marcados con 2 y agrégalos al final en orden inverso. El recorrido en preorden llega a todos los nodos del borde izquierdo antes que a cualquier hoja, porque el borde gira a la derecha solo donde no hay nada a su izquierda.

Algoritmo

Empieza por la raíz. Apila su hijo derecho con la marca 2 y después su hijo izquierdo con la marca 1.
Desapila un nodo. Añádelo si es una hoja o tiene la marca 1; añade a la lista derecha los nodos que no sean hojas y tengan la marca 2.
Apila su hijo derecho y después su hijo izquierdo, cada uno con la marca que le asigne la regla.
Cuando la pila esté vacía, añade la lista derecha en orden inverso.

def boundaryTraversal(root):
    n = len(root)

    def real(i):
        return i < n and root[i] != -1

    result = [root[0]]
    right = []  # the right boundary, top-down; it goes on the end reversed
    # Each entry is (index, edge): 1 = left boundary, 2 = right boundary, 0 = inside.
    stack = []
    if real(2):
        stack.append((2, 2))
    if real(1):
        stack.append((1, 1))
    while stack:
        i, edge = stack.pop()
        has_left, has_right = real(2 * i + 1), real(2 * i + 2)
        if not has_left and not has_right:
            result.append(root[i])  # a leaf; pre-order meets them left to right
        elif edge == 1:
            result.append(root[i])  # the left boundary, top-down
        elif edge == 2:
            right.append(root[i])
        # An edge passes to the child on its own side, or to an only child.
        # The right child goes on the stack first, so the left one comes out first.
        if has_right:
            stack.append((2 * i + 2, edge if edge == 2 or not has_left else 0))
        if has_left:
            stack.append((2 * i + 1, edge if edge == 1 or not has_right else 0))
    result.extend(reversed(right))
    return result

Errores comunes y casos límite

Enumerar un nodo dos veces. Un recorrido por aristas que no se detiene antes de su hoja enumera 1 dos veces en el ejemplo 1, y un árbol de un solo nodo no debe volver a enumerar su raíz como hoja.
Tomar el primer nodo de cada nivel como límite izquierdo. Si el hijo izquierdo de la raíz es una hoja y el subárbol derecho es más profundo, los niveles más profundos comienzan con nodos del subárbol derecho, pero el límite izquierdo está vacío.
Seguir solo los hijos izquierdos. En el ejemplo 2, el límite debe ir de 4 a su hijo derecho 6.
Recopilar las hojas nivel por nivel. El ejemplo 1 da después 1, 8, 4, 6.
En Lua y R, mantener los índices de los nodos basados en 0 para la aritmética 2i+1 y leer root[i + 1].

Preguntas frecuentes3

¿Qué es el recorrido del contorno de un árbol binario?

Enumera el contorno del árbol en sentido contrario a las agujas del reloj: la raíz, el borde izquierdo de arriba abajo, las hojas de izquierda a derecha y el borde derecho de abajo arriba. Los bordes excluyen sus hojas, así que ningún nodo aparece dos veces.

¿Cuál es la complejidad temporal del recorrido del límite?

O(n). Cada uno de los dos recorridos por los bordes sigue un camino, y el recorrido por las hojas visita cada nodo una vez. El espacio adicional es O(h) para la recursión o la pila.

¿El límite izquierdo siempre sigue a los hijos de la izquierda?

No. Se desplaza al hijo izquierdo cuando lo hay y al hijo derecho en caso contrario: el camino más externo que ves desde la izquierda. Si la raíz no tiene hijo izquierdo, el límite izquierdo está vacío.

def boundaryTraversal(root):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumento

root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]

Salida Esperada

[7, 3, 1, 4, 6, 8, 9]