Binary Tree Zigzag Level Order Traversal
Você recebe uma árvore binária armazenada no array root. A raiz fica no índice 0, os filhos do índice i ficam em 2*i+1 (à esquerda) e 2*i+2 (à direita), -1 marca uma posição vazia, e o array pode terminar com entradas extras -1.
Retorne os valores dos nós nível por nível, em ordem de zigue-zague: o nível da raiz da esquerda para a direita, o próximo da direita para a esquerda e assim por diante, alternando até o nível mais profundo. Isso também é chamado de percurso em ordem de nível em espiral.
Função
- rootinteger-array
- a árvore em ordem de heap, com -1 para uma posição vazia
- Retornainteger-2d-array
- uma lista de valores por nível, começando pelo nível superior e alternando entre da esquerda para a direita e da direita para a esquerda
Restrições
1 ≤ root.length ≤ 32767- Cada
root[i]é-1ou um valor com0 ≤ root[i] ≤ 104. - Os valores dos nós são distintos.
root[0]nunca é-1, então a árvore tem pelo menos um nó.- A matriz pode terminar com entradas
-1extras após o último nó. - Ambos os filhos de um espaço vazio também estão vazios, e a árvore tem no máximo
14níveis.
Exemplos
- Entrada
- root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]
- Saída
- [[8], [5, 12], [1, 9, 14], [11, 2, 4]]
- Explicação
- Lendo da esquerda para a direita, os níveis são
8;12, 5;1, 9, 14;4, 2, 11. Os níveis 1 e 3 são percorridos de trás para frente:[5, 12]e[11, 2, 4].
- Entrada
- root = [1, 2, 3, 4, 5, 6, 7, -1, -1]
- Saída
- [[1], [3, 2], [4, 5, 6, 7]]
- Explicação
- Uma árvore completa de três níveis: o nível do meio inverte para
[3, 2]e o terceiro segue da esquerda para a direita novamente. As duas entradas finais-1são os espaços vazios dos filhos de4.
- Entrada
- root = [5]
- Saída
- [[5]]
- Explicação
- Um nó único é um nível de um valor, lido em qualquer direção.
Para ir além
Você consegue colocar cada valor diretamente em seu lugar final na linha, sem inverter e sem usar uma segunda pilha?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Primeiro, colete os níveis, cada um da esquerda para a direita, como em uma travessia simples por ordem de nível. Quais dessas listas precisam ser alteradas e como?
Numere os níveis a partir de 0 na raiz. Os níveis ímpares são lidos de trás para frente. Inverter uma lista custa tanto quanto lê-la, então inverter esses níveis mantém tudo linear.
Para pular a inversão, mantenha o nível atual em uma pilha e empilhe os filhos em uma segunda pilha enquanto desempilha: primeiro o filho da esquerda ao ler da esquerda para a direita, primeiro o filho da direita ao ler da direita para a esquerda. A segunda pilha então desempilha o próximo nível na ordem necessária.
Solução
Os níveis vêm de uma busca em largura comum. A novidade está na direção: cada nível alternado sai invertido. Inverta as linhas ímpares depois de montá-las ou armazene cada nível em uma pilha, que devolve os itens na ordem oposta à das inserções.
Ordem por nível e, em seguida, inverta os níveis alternados
Intuição
Uma fila processada um nível por rodada produz cada nível da esquerda para a direita. Numere os níveis começando em 0 na raiz: o zigue-zague lê os níveis ímpares da direita para a esquerda, então inverter exatamente essas linhas fornece a resposta.
A busca visita cada nó uma vez, e cada inversão percorre cada valor mais uma vez, então o tempo é O(n).
Algoritmo
- Inicie uma fila com o índice
0. - Em cada rodada, salve o comprimento da fila
s, removasíndices da fila para uma nova linha e adicione os filhos existentes de cada um à fila, primeiro o da esquerda e depois o da direita. - Se a resposta já contiver um número ímpar de linhas, inverta a linha.
- Adicione a linha e continue até que a fila esteja vazia.
from collections import deque
def zigzagLevelOrder(root):
n = len(root)
levels = []
queue = deque([0]) # node indexes; the root is never empty
while queue:
row = []
for _ in range(len(queue)): # exactly the nodes of the current level
i = queue.popleft()
row.append(root[i])
for child in (2 * i + 1, 2 * i + 2):
if child < n and root[child] != -1:
queue.append(child)
if len(levels) % 2 == 1: # levels 1, 3, 5, ... read from right to left
row.reverse()
levels.append(row)
return levelsDuas pilhas
Intuição
Mantenha o nível atual em uma pilha que é desempilhada na direção em que o nível é lido, e empilhe os filhos de cada nó desempilhado em uma segunda pilha. Quando a pilha atual ficar vazia, a segunda conterá o próximo nível.
A ordem de empilhamento faz isso funcionar. Desempilhando da esquerda para a direita, empilhe o filho esquerdo de cada nó e, em seguida, o direito: o filho direito do nó mais à direita é empilhado por último, então o próximo nível é desempilhado pela extremidade direita. Desempilhando da direita para a esquerda, empilhe o filho direito e, em seguida, o esquerdo, e o filho esquerdo do nó mais à esquerda será empilhado por último.
Exemplo 1: desempilhe 8, empilhe 12, 5. Desempilhe 5, 12 e, em seguida, empilhe 14 de 5 e 9, 1 de 12. Desempilhe 1, 9, 14 e, em seguida, empilhe 4, 2 de 9 e 11 de 14. Desempilhe 11, 2, 4.
Cada nó é empilhado e desempilhado uma vez: tempo O(n), sem etapa de reversão.
Algoritmo
- Empilhe o índice
0da raiz e comece a ler da esquerda para a direita. - Enquanto a pilha não estiver vazia, retire todos os índices e coloque-os em uma nova linha; depois, empilhe os filhos existentes de cada nó retirado em uma segunda pilha: primeiro o esquerdo e depois o direito ao ler da esquerda para a direita; caso contrário, primeiro o direito e depois o esquerdo.
- Acrescente a linha à resposta.
- Faça da segunda pilha a pilha atual, inverta a direção e repita.
def zigzagLevelOrder(root):
n = len(root)
levels = []
current = [0] # a stack of node indexes; the root is never empty
left_to_right = True
while current:
row = []
upcoming = [] # the next level, pushed while this one pops
while current:
i = current.pop()
row.append(root[i])
# Push so that the next level pops out in its own direction.
if left_to_right:
children = (2 * i + 1, 2 * i + 2)
else:
children = (2 * i + 2, 2 * i + 1)
for child in children:
if child < n and root[child] != -1:
upcoming.append(child)
levels.append(row)
current = upcoming
left_to_right = not left_to_right
return levels
Armadilhas e casos extremos
- Inverter a ordem em que os filhos entram em uma única fila. Os irmãos trocam de posição, mas os pais mantêm a ordem: o terceiro nível do exemplo 1 resulta em
[9, 1, 14]. - Contar os níveis a partir de 1. Cada inversão fica um nível fora, e o exemplo 1 resulta em
[[8], [12, 5], [14, 9, 1], [4, 2, 11]]. - Usar a mesma ordem de inserção em todos os níveis da versão com duas pilhas. O terceiro nível do exemplo 1 então é removido como
[9, 1, 14]. - Inserir os filhos na pilha da qual você ainda está removendo elementos. Eles saem antes do restante do nível do pai.
- Ordenar uma linha em vez de invertê-la. O último nível do exemplo 1 precisa ser
[11, 2, 4], resultado que nenhuma ordenação produz.
Perguntas frequentes3
Qual é a diferença entre a travessia em zigue-zague e a travessia em ordem por nível?
Elas percorrem os mesmos níveis com os mesmos nós. A ordem por nível percorre cada nível da esquerda para a direita; a ordem em zigue-zague percorre cada segundo nível da direita para a esquerda, começando pelo nível abaixo da raiz. Ambas têm complexidade de tempo O(n).
O percurso em zigue-zague é o mesmo que o percurso em espiral de uma árvore?
Sim, os dois nomes descrevem o mesmo percurso. Alguns textos começam o segundo nível pela esquerda em vez de pela direita, o que apenas desloca as inversões em um nível. Aqui, o nível da raiz vai da esquerda para a direita, e o próximo vai da direita para a esquerda.
É possível fazer a ordem por níveis em zigue-zague com um deque?
Sim. Mantenha cada nível na deque na ordem da esquerda para a direita. Em um nível da esquerda para a direita, retire os nós do início e adicione os filhos deles, primeiro o da esquerda e depois o da direita, ao final. Em um nível da direita para a esquerda, retire os nós do final e adicione os filhos deles, primeiro o da direita e depois o da esquerda, ao início. A quantidade de nós retirada quando uma rodada começa ainda define o nível.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def zigzagLevelOrder(root):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumento
root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]
Saída Esperada
[[8], [5, 12], [1, 9, 14], [11, 2, 4]]