Construct Binary Tree from Preorder and Inorder Traversal

Q: Você consegue reconstruir uma árvore binária a partir das travessias em pré-ordem e pós-ordem?

Não, em geral. A pré-ordem [1, 2] e a pós-ordem [2, 1] são compatíveis tanto com um filho à esquerda quanto com um filho à direita, porque nenhuma das travessias coloca a raiz entre suas subárvores. O par é suficiente apenas para uma árvore binária estrita, em que cada nó tem zero ou dois filhos.

MédioPercurso em árvores Hashing Recursão

+10

Você recebe dois arrays, preorder e inorder, que listam os valores distintos da mesma árvore binária. O percurso em pré-ordem visita um nó, depois sua subárvore esquerda e, em seguida, sua subárvore direita. O percurso em ordem visita a subárvore esquerda, depois o nó e, em seguida, a subárvore direita.

Reconstrua a árvore e retorne-a como um array em ordem por níveis: a raiz no índice 0, os filhos do índice i nos índices 2i+1 (esquerda) e 2i+2 (direita), e -1 para cada posição vazia. O array termina no último nó, sem nenhum -1 no final.

Função

buildTree(preorder: integer-array, inorder: integer-array) → integer-array

preorderinteger-array: os valores em pré-ordem: nó, subárvore esquerda, subárvore direita
inorderinteger-array: os valores em ordem simétrica: subárvore esquerda, nó, subárvore direita
Retornainteger-array: a árvore em ordem por nível, com -1 para posições vazias e sem -1 no final

Restrições

1 ≤ preorder.length ≤ 3000
inorder.length == preorder.length
0 ≤ preorder[i] ≤ 10⁴, e todos os valores são distintos.
inorder contém os mesmos valores, e ambos os arrays descrevem a mesma árvore binária.
A profundidade da árvore é no máximo 14, então cada índice na resposta é menor que 2¹⁴-1 = 16383.

Exemplos

Entrada: preorder = [7, 3, 0, 9, 4, 6]inorder = [0, 3, 9, 7, 4, 6]
Saída: [7, 3, 4, 0, 9, -1, 6]
Explicação: A pré-ordem começa pela raiz, 7. Ela está na posição 3 da inorder, então 0, 3, 9 vão para a esquerda e 4, 6 vão para a direita. 4 tem apenas um filho à direita, 6, então o índice 5 permanece -1.

Entrada: preorder = [1, 2, 3]inorder = [2, 3, 1]
Saída: [1, 2, -1, -1, 3]
Explicação: A raiz 1 vem por último em inorder, então o índice 2 é -1. Entre 2, 3, preorder lista 2 primeiro e inorder coloca 3 depois dele, então 3 é seu filho direito, no índice 4.

Para ir além

Você consegue reconstruir a árvore sem recursão, em uma única passagem por preorder com uma pilha explícita?

Dicas

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

0 de 3 abertas

Solução

A pré-ordem fornece a raiz de cada subárvore: o primeiro valor de seu trecho. A ordem simétrica fornece a divisão: os valores antes da raiz vão para a esquerda, e os valores depois dela vão para a direita. A recursão em ambas as metades reconstrói a árvore, e um mapa de valores para posições na ordem simétrica torna a busca de cada raiz uma operação de uma etapa.

Divida recursivamente, procurando a raiz

Intuição

Em pré-ordem, a subárvore esquerda vem após sua raiz e ocupa uma entrada por valor, m-lo delas, em que m é a posição da raiz na ordem simétrica. A subárvore direita vem depois dela, então sua raiz fica em pre+1+(m-lo). No primeiro exemplo, a parte esquerda 0, 3, 9 tem três valores, então a subárvore direita começa no índice 4 da pré-ordem, o valor 4.

Uma profundidade de no máximo 14 mantém todos os índices de saída abaixo de 2^14-1. Preencha essa quantidade de células com -1, escreva cada valor no seu índice e remova as entradas -1 finais no fim.

Examinar cada intervalo da ordem simétrica em busca de sua raiz custa O(n·h): os intervalos em um mesmo nível não se sobrepõem, então um nível examina no máximo n entradas, no máximo 14 × 3000 = 42000 etapas neste caso. Sem limite de profundidade, uma árvore em forma de caminho torna isso O(n²).

Algoritmo

Crie out com 2^14-1 entradas, todas -1.
Escreva build(pre, lo, hi, h): se lo > hi, retorne. Caso contrário, escreva preorder[pre] em out[h].
Percorra inorder de lo até encontrar a posição m da raiz. A subárvore esquerda tem m-lo valores.
Chame build(pre+1, lo, m-1, 2*h+1) e build(pre+1+(m-lo), m+1, hi, 2*h+2).
Chame build(0, 0, n-1, 0), depois remova as entradas -1 finais e retorne o restante.

def buildTree(preorder, inorder):
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = lo
        while inorder[m] != value:  # find the root in the inorder range
            m += 1
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

    build(0, 0, len(inorder) - 1, 0)
    last = len(out) - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Divida recursivamente com um mapa de posições

Intuição

Os valores são distintos, então cada um tem exatamente uma posição em inorder. Registre essa posição em um mapa de valor para posição antes de a recursão começar, e cada busca pela raiz passa a levar uma etapa.

Construir o mapa leva O(n), e cada valor é então colocado uma vez com trabalho constante, então o tempo total é O(n). O mapa ocupa O(n) de espaço, e a recursão, um quadro por nível. Em C e R, os valores são no máximo 10^4, então um array simples com 10^4+1 entradas serve como mapa.

Algoritmo

Crie um mapa de cada valor de inorder para sua posição.
Crie out com 2^14-1 entradas, todas iguais a -1.
Em build(pre, lo, hi, h), retorne se lo > hi; caso contrário, escreva preorder[pre] em out[h] e consulte sua posição m no mapa.
Faça a recursão com build(pre+1, lo, m-1, 2*h+1) e build(pre+1+(m-lo), m+1, hi, 2*h+2).
Chame build(0, 0, n-1, 0), depois remova as entradas -1 finais e retorne o restante.

def buildTree(preorder, inorder):
    position = {value: i for i, value in enumerate(inorder)}  # value -> inorder index
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = position[value]
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

    build(0, 0, len(inorder) - 1, 0)
    last = len(out) - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Armadilhas e casos extremos

Iniciar a subárvore direita em pre+1+m em vez de pre+1+(m-lo). Funciona enquanto lo é 0, como na chamada inicial, e falha quando um intervalo começa mais adiante.
Descartar os espaços. Um filho ausente ainda ocupa sua posição, então o segundo exemplo retorna [1, 2, -1, -1, 3], não [1, 2, 3].
Deixar entradas -1 finais. Retornar todas as 2^14-1 células adiciona 16376 entradas -1 extras ao primeiro exemplo.
Copiar fatias dos dois arrays em cada chamada, o que adiciona O(n) por nível. Passe intervalos de índices.
Em Lua e R, os arrays começam em 1. Mantenha as posições baseadas em 0 para os cálculos e leia preorder[pre + 1] e out[h + 1].

Perguntas frequentes3

Por que você precisa tanto do percurso em pré-ordem quanto do percurso em ordem para reconstruir uma árvore binária?

A travessia em pré-ordem, sozinha, não determina a forma. A pré-ordem [1, 2] corresponde a uma árvore em que 2 é o filho esquerdo de 1 e a outra em que é o filho direito. A travessia em ordem resolve isso: [2, 1] coloca 2 à esquerda, [1, 2] à direita. Com valores distintos, o par descreve exatamente uma árvore.

Qual é a complexidade de tempo para construir uma árvore binária a partir das travessias em pré-ordem e em ordem?

Com um mapa de valores para posições em ordem simétrica, o tempo é O(n) e o espaço extra é O(n). Sem o mapa, percorrer cada intervalo em ordem simétrica para localizar sua raiz custa O(n·h), que se torna O(n²) em uma árvore com formato de caminho.

Você consegue reconstruir uma árvore binária a partir das travessias em pré-ordem e pós-ordem?

Não, em geral. A pré-ordem [1, 2] e a pós-ordem [2, 1] são compatíveis tanto com um filho à esquerda quanto com um filho à direita, porque nenhuma das travessias coloca a raiz entre suas subárvores. O par é suficiente apenas para uma árvore binária estrita, em que cada nó tem zero ou dois filhos.

def buildTree(preorder, inorder):
    # Escreva o código aqui

Teste #1

Teste #2

Argumentos

preorder = [7, 3, 0, 9, 4, 6]
inorder = [0, 3, 9, 7, 4, 6]

Saída Esperada

[7, 3, 4, 0, 9, -1, 6]