Subtree of Another Tree

Q: ¿Cuál es la complejidad temporal de Subtree of Another Tree?

Comparar desde cada nodo cuesta O(n·m) en el peor de los casos, donde n y m son los tamaños de los dos árboles. Comparar solo en los nodos cuya altura es igual a la altura de subRoot reduce el costo a O(n + m) , porque así cada nodo de root se recorre como máximo una vez.

Q: ¿Se puede resolver «Subtree of Another Tree» mediante búsqueda de cadenas?

Sí. Escribe cada árbol en preorden, con # para cada hijo vacío y un separador antes de cada valor: ,2,1,#,#,3,#,# . subRoot es un subárbol exactamente cuando su cadena aparece dentro de la cadena de root , y KMP lo encuentra en O(n + m) . Sin los marcadores, distintas formas producen la misma cadena; sin separadores, 12 contiene 2 .

FácilRecorrido de árboles Recursión

+10

Se te dan dos árboles binarios, root y subRoot, cada uno almacenado en un arreglo en orden por niveles: la raíz en el índice 0, los hijos del índice i en 2*i+1 (izquierda) y 2*i+2 (derecha), y -1 para una posición vacía. Un arreglo puede terminar con entradas -1 adicionales.

Devuelve true si algún nodo de root, junto con todos sus descendientes, tiene exactamente la misma forma y los mismos valores que subRoot, y false en caso contrario. También se considera el árbol completo root.

Función

isSubtree(root: integer-array, subRoot: integer-array) → boolean

rootinteger-array: el árbol que se va a buscar, en orden por niveles, con -1 para una posición vacía
subRootinteger-array: el árbol que se debe buscar, en el mismo formato
Devuelveboolean: verdadero si subRoot aparece en root como un nodo con todos sus descendientes, falso en caso contrario

Restricciones

1 ≤ root.length ≤ 32767 y 1 ≤ subRoot.length ≤ 32767
Cada entrada es -1 o un valor de 0 a 10⁴.
root[0] y subRoot[0] nunca son -1, así que ambos árboles tienen al menos un nodo.
Cualquiera de los dos arreglos puede terminar con entradas adicionales -1 después de su último nodo.
Ambos hijos de un espacio vacío también están vacíos, y cada árbol tiene una profundidad de como máximo 14.
Los valores pueden repetirse.

Ejemplos

Entrada: root = [6, 2, 8, 1, 3, -1, 9]subRoot = [2, 1, 3]
Salida: true
Explicación: El nodo 2 en el índice 1 tiene como hijos 1 y 3, y ambos son hojas. Eso es exactamente subRoot.

Entrada: root = [6, 2, 8, 1, 3, -1, 9, -1, -1, 0]subRoot = [2, 1, 3]
Salida: false
Explicación: El 3 debajo del nodo 2 ahora tiene un hijo 0. Un subárbol incluye a todos los descendientes, así que el nodo 2 aporta cuatro nodos frente a los tres de subRoot, y ningún otro nodo contiene un 2.

Entrada: root = [5, 5, 7]subRoot = [5]
Salida: true
Explicación: La raíz 5 tiene dos hijos, así que no coincide con el nodo único 5. El 5 en el índice 1 es una hoja y coincide.

Para ir más allá

¿Puedes calcular una huella digital de cada subárbol a partir de su valor y de las huellas digitales de sus hijos, para que compararlo con subRoot cueste O(1)? ¿Qué haces cuando colisionan dos subárboles diferentes?

Pistas

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

0 de 3 abiertas

Solución

El problema tiene dos partes: decidir si dos árboles son idénticos y elegir dónde en root realizar esa comprobación. Solo puede coincidir un nodo cuya altura sea igual a la altura de subRoot, y los nodos de una misma altura nunca se superponen, así que comprobar solo esos nodos recorre cada nodo de root como máximo una vez.

Compara en cada nodo

Intuición

Una posición i es válida cuando i está dentro del array y el valor que contiene no es -1. Dos árboles son idénticos cuando ambos están vacíos, o cuando sus raíces contienen el mismo valor y sus subárboles izquierdo y derecho son idénticos. same(i, j) recorre root desde i y subRoot desde j al mismo tiempo. Si subRoot aparece en root, su raíz se encuentra en algún nodo, así que prueba same(i, 0) desde cada i válido.

Una coincidencia parcial puede ejecutarse durante hasta m pasos antes de fallar, desde cada uno de los n nodos: O(n·m). Aquí, el límite de profundidad lo acota: un nodo solo se recorre en las comprobaciones que empiezan en él o por encima de él, como máximo 14.

Algoritmo

Escribe same(i, j). Si la posición i en root y la posición j en subRoot están vacías, devuelve true; si solo una está vacía, devuelve false.
Si los dos valores son distintos, devuelve false. En caso contrario, devuelve same(2*i+1, 2*j+1) y same(2*i+2, 2*j+2).
Devuelve true si se cumple same(i, 0) para algún índice real i de root, y false en caso contrario.

def isSubtree(root, subRoot):
    n, m = len(root), len(subRoot)

    def same(i, j):
        # True if the subtree at root[i] equals the subtree at subRoot[j].
        a = i < n and root[i] != -1
        b = j < m and subRoot[j] != -1
        if not a or not b:
            return a == b  # two empty spots match, one empty spot does not
        if root[i] != subRoot[j]:
            return False
        return same(2 * i + 1, 2 * j + 1) and same(2 * i + 2, 2 * j + 2)

    # Try every real node of root as the top of a match.
    for i in range(n):
        if root[i] != -1 and same(i, 0):
            return True
    return False

Compara solo donde las alturas coincidan

Intuición

Los árboles idénticos tienen la misma altura, que se cuenta como el número de nodos en el camino más largo hacia abajo. Así que solo vale la pena comprobar los nodos de root cuya altura sea igual a la altura de subRoot. En el primer ejemplo, subRoot tiene altura 2, y en root solo la tienen 2 y 8.

Un nodo es más alto que todos los nodos que tiene debajo, así que dos nodos de la misma altura nunca están uno dentro del otro. Cada comprobación recorre solo el subárbol de su nodo inicial, así que, en conjunto, las comprobaciones recorren cada nodo de root como máximo una vez.

Los hijos tienen índices mayores que los de su padre, así que un recorrido desde el último índice hacia atrás llega a ambos hijos antes que al padre. Los dos recorridos para calcular la altura y las comprobaciones toman un tiempo de O(n + m).

Algoritmo

Rellena un arreglo de alturas para cada árbol, recorriéndolo desde el último índice hasta 0: un espacio vacío recibe 0; un nodo real recibe 1 más la mayor altura de sus dos hijos.
Para cada índice i de root cuya altura sea igual a la altura en el índice 0 de subRoot, ejecuta same(i, 0) y devuelve true si se cumple.
Devuelve false.

def isSubtree(root, subRoot):
    n, m = len(root), len(subRoot)

    def same(i, j):
        # True if the subtree at root[i] equals the subtree at subRoot[j].
        a = i < n and root[i] != -1
        b = j < m and subRoot[j] != -1
        if not a or not b:
            return a == b  # two empty spots match, one empty spot does not
        if root[i] != subRoot[j]:
            return False
        return same(2 * i + 1, 2 * j + 1) and same(2 * i + 2, 2 * j + 2)

    def heights(tree):
        # Children sit at larger indexes, so a backward scan finishes them first.
        h = [0] * len(tree)
        for i in range(len(tree) - 1, -1, -1):
            if tree[i] != -1:
                left = h[2 * i + 1] if 2 * i + 1 < len(tree) else 0
                right = h[2 * i + 2] if 2 * i + 2 < len(tree) else 0
                h[i] = 1 + max(left, right)
        return h

    target = heights(subRoot)[0]
    rootHeights = heights(root)
    # Only a node of the same height can match, and no two such nodes overlap.
    for i in range(n):
        if rootHeights[i] == target and same(i, 0):
            return True
    return False

Errores comunes y casos límite

Aceptar una coincidencia parcial, como en el segundo ejemplo. same debe fallar cuando root tiene un nodo donde subRoot tiene un espacio vacío.
Detenerse en el primer nodo con el valor correcto. En el tercer ejemplo, la raíz 5 falla y la hoja 5 que está debajo coincide.
Comparar segmentos de los dos arreglos. Los nodos de un subárbol se distribuyen en muchos niveles, y cualquiera de los arreglos puede terminar con entradas adicionales -1. Un índice que está más allá del final es un espacio vacío, como un -1.
En Lua y R, mantener los índices de los nodos basados en 0 para la operación aritmética 2*i+1 y leer root[i + 1].

Preguntas frecuentes3

¿Cuál es la complejidad temporal de Subtree of Another Tree?

Comparar desde cada nodo cuesta O(n·m) en el peor de los casos, donde n y m son los tamaños de los dos árboles. Comparar solo en los nodos cuya altura es igual a la altura de subRoot reduce el costo a O(n + m), porque así cada nodo de root se recorre como máximo una vez.

¿Se puede resolver «Subtree of Another Tree» mediante búsqueda de cadenas?

Sí. Escribe cada árbol en preorden, con # para cada hijo vacío y un separador antes de cada valor: ,2,1,#,#,3,#,#. subRoot es un subárbol exactamente cuando su cadena aparece dentro de la cadena de root, y KMP lo encuentra en O(n + m). Sin los marcadores, distintas formas producen la misma cadena; sin separadores, 12 contiene 2.

¿Cuenta un nodo que coincide con subRoot pero tiene hijos adicionales?

No. Un subárbol es un nodo junto con todos sus descendientes, así que todos los nodos que están bajo la coincidencia también deben aparecer en subRoot. En el segundo ejemplo, el 0 adicional bajo el 3 hace que la respuesta sea false.

def isSubtree(root, subRoot):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

root = [6, 2, 8, 1, 3, -1, 9]
subRoot = [2, 1, 3]

Salida Esperada

true