Invert Binary Tree

Q: Qual é a complexidade de tempo para inverter uma árvore binária?

Cada nó é visitado uma vez, então o tempo é O(n) . Uma solução recursiva usa O(h) de espaço na pilha para uma árvore de profundidade h , e uma solução baseada em fila usa O(w) para o nível mais largo. Nesta versão com array, a própria resposta é um novo array, o que adiciona O(n) .

FácilPercurso em árvores

+10

Você recebe uma árvore binária armazenada no array tree em ordem por níveis. A raiz fica no índice 0, os filhos do nó no índice i ficam em 2*i+1 (esquerdo) e 2*i+2 (direito), -1 marca uma posição vazia, e o array pode terminar com entradas extras -1.

Inverta a árvore: troque os filhos esquerdo e direito de cada nó, para que a árvore inteira se torne sua imagem espelhada. Retorne a árvore invertida no mesmo formato, sem entradas -1 no final.

Função

invertTree(tree: integer-array) → integer-array

treeinteger-array: a árvore binária em ordem por nível, com -1 para uma posição vazia
Retornainteger-array: árvore espelhada em ordem por nível, sem entradas -1 no final

Restrições

1 ≤ tree.length ≤ 16383
Cada tree[i] é -1 ou um valor com 0 ≤ tree[i] ≤ 1000.
tree[0] nunca é -1, então a árvore tem pelo menos um nó.
The array pode terminar com entradas -1 extras após o último nó.
Ambos os filhos de um espaço vazio também estão vazios, e a profundidade é no máximo 14.

Exemplos

Entrada: tree = [5, 3, 8, 1, 4, -1, 9]
Saída: [5, 8, 3, 9, -1, 4, 1]
Explicação: Os filhos da raiz 3 e 8 trocam de lugar. Abaixo deles, o 1 e o 4 que estavam abaixo de 3 voltam como 4 e 1, e 8, que tinha apenas um filho à direita, 9, agora o tem à esquerda.

Entrada: tree = [2, 7, -1, 6]
Saída: [2, -1, 7, -1, -1, -1, 6]
Explicação: A sequência 2, 7, 6 pende para a esquerda, e sua imagem espelhada pende para a direita. O 7 passa do índice 1 para o índice 2, e o 6, do índice 3 para o índice 6; portanto, a resposta é mais longa que a entrada, com -1 em cada posição vazia antes do último nó.

Entrada: tree = [1, -1, -1]
Saída: [1]
Explicação: Um único nó é seu próprio espelho. As duas entradas -1 são preenchimento, e a resposta elimina todos os -1 no final.

+14 testes ocultos ao enviar

Para ir além

Como você verificaria se uma árvore é o seu próprio espelho, usando os mesmos pares de índices, mas sem construir a cópia invertida?

Dicas

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

0 de 3 abertas

Solução

Espelhar uma árvore significa trocar a subárvore esquerda e a direita de cada nó, até o fim. Com objetos de nó, isso significa uma troca por nó. Nesta representação em array, a posição de um nó é seu índice, então trocar duas subárvores significa mover todos os nós dentro delas. A solução é construir a resposta em um novo array e copiar cada nó diretamente para seu índice espelhado, levando pares de índices durante uma travessia: onde o nó está agora e para onde vai.

Recursão que coloca cada nó em seu índice espelhado

Intuição

Primeiro, como percorrer o array. O nó no índice i tem seu filho esquerdo em 2*i+1 e seu filho direito em 2*i+2. Um filho só existe se seu índice estiver dentro do array e o valor nessa posição não for -1. Em [5, 3, 8, 1, 4, -1, 9], a raiz 5 tem 3 e 8 nos índices 1 e 2, e o 8 no índice 2 tem uma posição esquerda vazia em 5 e o 9 em 6.

Agora, o espelhamento. A raiz permanece no índice 0. A subárvore esquerda de um nó se torna a subárvore direita de sua cópia espelhada, e sua subárvore direita se torna a esquerda. Portanto, se o nó no índice src ficar no índice dst na resposta, seu filho esquerdo ficará em 2*dst+2 e seu filho direito em 2*dst+1. Escreva place(src, dst): copie o valor e, em seguida, chame place(2*src+1, 2*dst+2) e place(2*src+2, 2*dst+1). Uma posição vazia retorna imediatamente. No primeiro exemplo, o 3 no índice 1 fica no índice 2, então seu filho esquerdo 1 fica no índice 6 e seu filho direito 4 no índice 5.

Um nó nunca muda de nível, então seu índice espelhado permanece no mesmo nível que o original. Arredonde o comprimento para cima até atingir um nível completo (1, 3, 7, 15, ...), preencha essa quantidade de posições com -1 e remova as entradas finais -1 no fim. No segundo exemplo, o comprimento 4 é arredondado para 7, o que deixa espaço para o 6 no índice 6.

Cada nó é posicionado uma vez, e a saída é preenchida e cortada uma vez: tempo O(n) para um array de comprimento n. A saída ocupa memória O(n), e a pilha de chamadas, O(h), no máximo 14 quadros aqui, o que torna a recursão segura neste problema.

Algoritmo

Arredonde o comprimento para cima até size = 2^k - 1 e preencha uma saída desse tamanho com -1.
Escreva place(src, dst): se src estiver além do fim ou tree[src] for -1, retorne.
Caso contrário, defina out[dst] = tree[src] e, em seguida, chame place(2*src+1, 2*dst+2) e place(2*src+2, 2*dst+1).
Chame place(0, 0), descarte as entradas -1 finais e retorne a saída.

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size

    def place(src, dst):
        if src >= n or tree[src] == -1:
            return
        out[dst] = tree[src]
        place(2 * src + 1, 2 * dst + 2)  # the left subtree goes to the right
        place(2 * src + 2, 2 * dst + 1)  # the right subtree goes to the left

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

Busca em largura com uma fila de pares de índices

Intuição

Os mesmos pares funcionam sem recursão. Coloque (0, 0) em uma fila: a raiz e a posição para onde ela vai. Retire um par (src, dst) do início, copie tree[src] para out[dst] e coloque na fila cada filho existente com seu destino invertido: o filho esquerdo 2*src+1 com 2*dst+2, o filho direito 2*src+2 com 2*dst+1.

Essa é a inversão iterativa clássica. Com objetos de nós, você retira um nó da fila, troca seus dois filhos e os coloca na fila. Aqui, a troca é feita no índice de destino, porque o array não consegue trocar duas subárvores inteiras em uma única etapa. Cada nó existente entra na fila uma vez, levando consigo a posição exata a que pertence, então a saída acaba contendo cada nó em sua posição espelhada. No primeiro exemplo, os pares são (0, 0), (1, 2), (2, 1), (3, 6), (4, 5), (6, 3).

O tempo é O(n). A fila armazena no máximo um nível e um pouco mais, O(w) para o nível mais largo w, além da saída O(n). Não há pilha de chamadas que possa transbordar, então esta versão se aplica sem alterações a árvores profundas baseadas em ponteiros.

Algoritmo

Arredonde o comprimento para cima até o próximo nível inteiro e preencha uma saída desse tamanho com -1.
Coloque o par (0, 0) em uma fila.
Remova o par (src, dst) do início da fila e defina out[dst] = tree[src].
Enfileire (2*src+1, 2*dst+2) e (2*src+2, 2*dst+1) para cada filho que esteja dentro do array e não seja -1.
Quando a fila estiver vazia, remova as entradas -1 finais e retorne a saída.

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size
    queue = [(0, 0)]  # pairs: index in tree, index of its mirrored spot in out
    head = 0
    while head < len(queue):
        src, dst = queue[head]
        head += 1
        out[dst] = tree[src]
        left, right = 2 * src + 1, 2 * src + 2
        if left < n and tree[left] != -1:
            queue.append((left, 2 * dst + 2))  # the left child goes to the right
        if right < n and tree[right] != -1:
            queue.append((right, 2 * dst + 1))  # the right child goes to the left
    last = size - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Armadilhas e casos extremos

O espelhamento em si é fácil de descrever. Os bugs vêm do array: seu tamanho, seu fim e o que realmente é movido ao trocar duas entradas.

Trocar tree[2*i+1] e tree[2*i+2] no próprio array. Isso troca dois valores, mas não as subárvores abaixo deles. Trocar os índices 1 e 2 no primeiro exemplo deixa 1 e 4 pendurados abaixo de 8.
Fazer a saída ter o mesmo tamanho da entrada. Um nó espelhado pode cair depois do último índice da entrada, como acontece com o 6 no segundo exemplo. Dimensione a saída para níveis completos.
Esquecer de remover o excesso. A resposta não tem -1 no final, tanto para entradas preenchidas quanto para árvores cujo espelhamento termina antes do que a entrada terminava.
Inverter o array inteiro. Isso mistura os níveis: a última folha se tornaria a raiz.
Pular a verificação dos limites. Um índice de filho pode ultrapassar o fim da entrada, porque o array pode terminar logo após o último nó.
Confundir o deslocamento em Lua e R, em que os arrays começam em 1. Mantenha os índices baseados em 0 para a aritmética de 2*i+1 e leia tree[i + 1].

Perguntas frequentes4

O que significa inverter uma árvore binária?

Inverter uma árvore binária a transforma em sua imagem espelhada: em cada nó, as subárvores esquerda e direita trocam de lugar. A raiz permanece onde está, a folha mais à esquerda se torna a mais à direita, e uma cadeia à esquerda se torna uma cadeia à direita. Inverter duas vezes restaura a árvore original.

Qual é a complexidade de tempo para inverter uma árvore binária?

Cada nó é visitado uma vez, então o tempo é O(n). Uma solução recursiva usa O(h) de espaço na pilha para uma árvore de profundidade h, e uma solução baseada em fila usa O(w) para o nível mais largo. Nesta versão com array, a própria resposta é um novo array, o que adiciona O(n).

Como inverter uma árvore binária sem recursão?

Use uma fila ou uma pilha. Comece pela raiz e, cada vez que retirar um nó, troque seus filhos esquerdo e direito de lugar e insira os filhos. Cada nó é invertido uma vez, em qualquer ordem em que a estrutura os forneça. Na representação em array, em vez disso, coloque em uma fila pares de índices e escreva cada nó diretamente em sua posição espelhada.

Por que inverter uma árvore binária inverte cada nível?

O espelhamento inverte a esquerda e a direita em todos os lugares, então os nós de cada nível aparecem na ordem oposta. No armazenamento em ordem por nível, isso significa que o trecho do array correspondente a cada nível é invertido: o trecho [1, 4, -1, 9] do primeiro exemplo resulta em [9, -1, 4, 1]. Inverter cada nível, depois de preencher o último com -1, é uma terceira solução O(n) que só funciona para esse layout de array.

Python

def invertTree(tree):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

tree = [5, 3, 8, 1, 4, -1, 9]

Esperado

[5, 8, 3, 9, -1, 4, 1]