Subtree of Another Tree

Q: Qual é a complexidade de tempo de Subtree of Another Tree?

Comparar a partir de cada nó custa O(n·m) no pior caso, em que n e m são os tamanhos das duas árvores. Comparar apenas nos nós cuja altura é igual à altura de subRoot reduz o custo para O(n + m) , porque cada nó de root é percorrido no máximo uma vez.

Q: É possível resolver Subtree of Another Tree usando correspondência de strings?

Sim. Escreva cada árvore em pré-ordem, usando # para cada filho vazio e um separador antes de cada valor: ,2,1,#,#,3,#,# . subRoot é uma subárvore exatamente quando sua string aparece dentro da string de root , e o KMP a encontra em O(n + m) . Sem os marcadores, formatos diferentes geram a mesma string; sem separadores, 12 contém 2 .

FácilPercurso em árvores Recursão

+10

Você recebe duas árvores binárias, root e subRoot, cada uma armazenada em um array em ordem por nível: a raiz no índice 0, os filhos do índice i em 2*i+1 (esquerdo) e 2*i+2 (direito), e -1 para uma posição vazia. Um array pode terminar com entradas extras -1.

Retorne true se algum nó de root, com todos os seus descendentes, tiver exatamente a mesma forma e os mesmos valores que subRoot, e false caso contrário. A árvore inteira root também conta.

Função

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

rootinteger-array: a árvore a ser pesquisada, em ordem por nível, com -1 para uma posição vazia
subRootinteger-array: a árvore a ser procurada, no mesmo formato
Retornaboolean: true se subRoot aparece em root como um nó com todos os seus descendentes, false caso contrário

Restrições

1 ≤ root.length ≤ 32767 e 1 ≤ subRoot.length ≤ 32767
Cada entrada é -1 ou um valor de 0 a 10⁴.
root[0] e subRoot[0] nunca são -1, então ambas as árvores têm pelo menos um nó.
Qualquer um dos arrays pode terminar com entradas -1 extras após seu último nó.
Ambos os filhos de um espaço vazio também estão vazios, e cada árvore tem profundidade de no máximo 14.
Os valores podem se repetir.

Exemplos

Entrada: root = [6, 2, 8, 1, 3, -1, 9]subRoot = [2, 1, 3]
Saída: true
Explicação: O nó 2 no índice 1 tem os filhos 1 e 3, e ambos são folhas. Isso é exatamente subRoot.

Entrada: root = [6, 2, 8, 1, 3, -1, 9, -1, -1, 0]subRoot = [2, 1, 3]
Saída: false
Explicação: O 3 abaixo do nó 2 agora tem um filho 0. Uma subárvore inclui todos os descendentes, então o nó 2 contém quatro nós, contra os três de subRoot, e nenhum outro nó contém um 2.

Entrada: root = [5, 5, 7]subRoot = [5]
Saída: true
Explicação: A raiz 5 tem dois filhos, então não corresponde ao nó único 5. O 5 no índice 1 é uma folha e corresponde.

Para ir além

Você consegue criar uma impressão digital de cada subárvore a partir de seu valor e das impressões digitais de seus filhos, de modo que uma comparação com subRoot custe O(1)? O que você faz quando duas subárvores diferentes colidem?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

O problema tem duas partes: decidir se duas árvores são idênticas e escolher onde em root executar essa verificação. Apenas um nó cuja altura seja igual à altura de subRoot pode corresponder, e nós de uma mesma altura nunca se sobrepõem, então verificar apenas esses nós percorre cada nó de root no máximo uma vez.

Compare em cada nó

Intuição

Uma posição i é válida quando i está dentro do array e o valor ali não é -1. Duas árvores são idênticas quando ambas estão vazias ou quando seus nós do topo contêm o mesmo valor e suas subárvores esquerda e direita são idênticas. same(i, j) percorre root a partir de i e subRoot a partir de j passo a passo. Se subRoot aparece em root, seu nó do topo está em algum nó; então, tente same(i, 0) a partir de cada i válido.

Uma correspondência quase exata pode levar até m passos antes de falhar, para cada um dos n nós: O(n·m). Aqui, o limite de profundidade restringe isso: um nó só é percorrido pelas verificações que começam nele ou acima dele, no máximo 14.

Algoritmo

Escreva same(i, j). Se a posição i em root e a posição j em subRoot estiverem ambas vazias, retorne true; se exatamente uma estiver vazia, retorne false.
Se os dois valores forem diferentes, retorne false. Caso contrário, retorne same(2*i+1, 2*j+1) e same(2*i+2, 2*j+2).
Retorne true se same(i, 0) for verdadeiro para algum índice válido i de root, e false caso contrário.

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

Compare apenas onde as alturas correspondem

Intuição

Árvores idênticas têm a mesma altura, contada como o número de nós no caminho mais longo para baixo. Portanto, só vale a pena verificar os nós de root cuja altura é igual à altura de subRoot. No primeiro exemplo, subRoot tem altura 2, e, em root, apenas os nós 2 e 8 têm essa altura.

Um nó é mais alto do que todos os nós abaixo dele, então dois nós de mesma altura nunca ficam um dentro do outro. Cada verificação percorre apenas a subárvore do nó inicial, portanto, juntas, as verificações percorrem cada nó de root no máximo uma vez.

Os filhos ficam em índices maiores do que o pai, então uma varredura do último índice para o primeiro alcança os dois filhos antes do pai. As duas varreduras de altura e as verificações levam O(n + m) de tempo.

Algoritmo

Preencha um array de alturas para cada árvore, percorrendo os índices do último até 0: uma posição vazia recebe 0, um nó real recebe 1 mais a maior altura entre seus dois filhos.
Para cada índice i de root cuja altura seja igual à altura no índice 0 de subRoot, execute same(i, 0) e retorne true se a condição for satisfeita.
Retorne 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

Armadilhas e casos extremos

Aceitar uma correspondência parcial, como no segundo exemplo. same deve falhar quando root tiver um nó em uma posição onde subRoot tiver uma posição vazia.
Parar no primeiro nó com o valor correto. No terceiro exemplo, a raiz 5 falha e a folha 5 abaixo dela corresponde.
Comparar fatias dos dois arrays. Os nós de uma subárvore se distribuem por vários níveis, e qualquer um dos arrays pode terminar com entradas -1 extras. Um índice além do fim é uma posição vazia, como um -1.
Em Lua e R, mantenha os índices dos nós começando em 0 para a operação aritmética 2*i+1 e leia root[i + 1].

Perguntas frequentes3

Qual é a complexidade de tempo de Subtree of Another Tree?

Comparar a partir de cada nó custa O(n·m) no pior caso, em que n e m são os tamanhos das duas árvores. Comparar apenas nos nós cuja altura é igual à altura de subRoot reduz o custo para O(n + m), porque cada nó de root é percorrido no máximo uma vez.

É possível resolver Subtree of Another Tree usando correspondência de strings?

Sim. Escreva cada árvore em pré-ordem, usando # para cada filho vazio e um separador antes de cada valor: ,2,1,#,#,3,#,#. subRoot é uma subárvore exatamente quando sua string aparece dentro da string de root, e o KMP a encontra em O(n + m). Sem os marcadores, formatos diferentes geram a mesma string; sem separadores, 12 contém 2.

Um nó que corresponde a subRoot, mas tem filhos extras, conta?

Não. Uma subárvore é um nó junto com todos os seus descendentes, então todos os nós abaixo do que corresponde também devem aparecer em subRoot. No segundo exemplo, o 0 extra abaixo do 3 faz com que a resposta seja false.

def isSubtree(root, subRoot):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

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

Saída Esperada

true