Binary Tree Level Order Traversal

Q: Qual é a complexidade de tempo da travessia em nível de uma árvore binária?

Tanto a solução em largura quanto a solução em profundidade visitam cada nó uma vez, então executam em tempo O(n) para n nós. A própria resposta contém n valores, então o espaço é O(n) . Além disso, a fila contém, no máximo, aproximadamente a quantidade de nós do nível mais largo, e a recursão, no máximo, a altura da árvore.

Q: Como saber onde um nível termina em uma busca em largura?

Leia o tamanho da fila no início de cada rodada. Nesse momento, a fila contém exatamente os nós de um nível, então retirar essa quantidade de nós remove o nível e nada mais. Duas outras maneiras também funcionam: manter o nível atual e o próximo nível em duas listas separadas ou inserir um marcador após cada nível.

Q: É possível fazer uma travessia em ordem por nível com busca em profundidade?

Sim. Passe a cada nó sua profundidade e acrescente seu valor à lista correspondente a essa profundidade. Desde que a travessia visite a subárvore esquerda antes da direita, todas as listas ficam em ordem da esquerda para a direita. Também é O(n) ; a busca em largura se encaixa melhor, pois produz os níveis em ordem.

Q: A matriz já está armazenada nível por nível. Que tal lê-la em fatias?

Para esse formato, funciona assim: o nível d ocupa os índices 2^d-1 a 2^(d+1)-2 , então você pode coletar os valores não vazios de cada intervalo e parar no primeiro intervalo sem nenhum. Em uma entrevista, porém, a árvore geralmente vem como objetos de nós com ponteiros para a esquerda e para a direita, sem índices para fatiar. A travessia baseada em fila é o que se aplica a esse formato e a variantes como a ordem em zigue-zague ou a visualização do lado direito.

MédioPercurso em árvores Fila

+10

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

Retorne os valores dos nós nível por nível: uma lista com o valor da raiz, depois uma lista com os valores um nível abaixo, da esquerda para a direita, e assim por diante até o nível mais profundo.

Função

levelOrder(tree: integer-array) → integer-2d-array

treeinteger-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 mais alto, cada uma da esquerda para a direita

Restrições

1 ≤ tree.length ≤ 32767
Cada tree[i] é -1 ou um valor tal que 0 ≤ tree[i] ≤ 1000.
tree[0] nunca é -1, então a árvore tem pelo menos um nó.
O 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 = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
Saída: [[4], [9, 2], [6, 8, 5], [3]]
Explicação: A raiz 4 tem os filhos 9 e 2 nos índices 1 e 2. O índice 3 está vazio, então o terceiro nível é 6 (índice 4, abaixo de 9), seguido por 8 e 5 (índices 5 e 6, abaixo de 2). O 3 no índice 9 é o filho esquerdo de 6, sozinho no quarto nível.

Entrada: tree = [7, -1, -1]
Saída: [[7]]
Explicação: Ambos os filhos da raiz são -1, então a árvore é o único nó 7 e tem um nível.

Entrada: tree = [1, 3, -1, 5, -1, -1, -1]
Saída: [[1], [3], [5]]
Explicação: Cada nó tem apenas um filho à esquerda: 3 no índice 1 e 5 no índice 3. Cada nível contém um valor, e as entradas finais -1 não acrescentam nada.

+15 testes ocultos ao enviar

Para ir além

Você consegue retornar os níveis em ordem zigue-zague, o primeiro da esquerda para a direita, o segundo da direita para a esquerda e assim por diante, sem ordenar nenhum nível?

Dicas

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

0 de 3 abertas

Solução

Cada nível precisa ser retornado como sua própria lista, ordenada da esquerda para a direita. Uma busca em largura com uma fila visita os nós exatamente nessa ordem. A ideia adicional é saber onde um nível termina: no início de cada rodada, a fila contém o nível atual inteiro e nada mais, então seu tamanho informa quantos nós devem ser processados. Uma busca em profundidade também funciona, desde que mantenha a profundidade de cada nó e percorra primeiro a esquerda e depois a direita.

Busca em profundidade, organizada por profundidade

Intuição

Primeiro, vamos percorrer o array. O filho esquerdo do índice i está em 2i+1 e o filho direito em 2i+2. Um filho está ausente quando seu índice ultrapassa o fim do array ou contém -1. No exemplo 1, os filhos de 9 (índice 1) estão nos índices 3 e 4, que contêm -1 e 6, então 9 tem apenas um filho à direita.

Agora percorra a árvore em profundidade e passe a cada nó sua profundidade, sendo 0 para a raiz. Mantenha uma lista por profundidade. Quando chegar a um nó na profundidade d, acrescente seu valor à lista d; se houver apenas d listas até então, este é o primeiro nó de um novo nível, então primeiro crie uma nova lista.

Por que cada nível fica da esquerda para a direita? O percurso termina toda a subárvore esquerda de um nó antes de entrar na subárvore direita. Considere dois nós no mesmo nível: no ponto em que seus caminhos a partir da raiz se bifurcam, um segue à esquerda e o outro à direita, e o percurso chega primeiro ao da esquerda. No exemplo 1, a ordem é 4, 9, 6, 3, 2, 8, 5, que preenche as listas como [4], [9, 2], [6, 8, 5], [3].

Cada nó é visitado uma vez, então o tempo é O(n) para n nós, e as listas contêm n valores. A recursão tem profundidade igual à da árvore, no máximo 15 níveis aqui. A versão em R usa uma pilha explícita, empilhando o filho direito antes do esquerdo para que o esquerdo seja removido primeiro, e então agrupa os valores por profundidade com split.

Algoritmo

Crie uma lista vazia de níveis.
Visite a raiz com profundidade 0.
No nó i com profundidade d, pare se i estiver além do fim ou se tree[i] for -1.
Se houver apenas d listas, adicione uma vazia. Acrescente tree[i] à lista d.
Visite 2i+1 e, em seguida, 2i+2, ambos com profundidade d+1.

def levelOrder(tree):
    n = len(tree)
    levels = []

    def visit(i, depth):
        if i >= n or tree[i] == -1:
            return
        if depth == len(levels):  # the first node seen on this level
            levels.append([])
        levels[depth].append(tree[i])
        # Left before right, so every level fills from left to right.
        visit(2 * i + 1, depth + 1)
        visit(2 * i + 2, depth + 1)

    visit(0, 0)
    return levels

Busca em largura, um nível por rodada

Intuição

Uma fila devolve os valores na ordem em que eles entraram. Coloque a raiz na fila. Em seguida, retire repetidamente um nó e coloque seus filhos na fila, primeiro o filho esquerdo. Cada nó do nível d+1 entra na fila quando seu pai no nível d sai dela, portanto todos os nós do nível d saem antes de qualquer nó do nível d+1, e, dentro de um nível, os nós saem da esquerda para a direita.

Isso produz um fluxo de valores em ordem por nível. Para separá-lo em níveis, leia o tamanho da fila no início de uma rodada. Nesse momento, a fila contém exatamente o nível atual: o nível anterior já saiu e nenhum nó do próximo nível chegou. Retire essa quantidade de nós e coloque-os em uma lista. Os filhos que eles adicionam pertencem à próxima rodada.

No exemplo 1, a fila começa como [4]: retire 1 nó, linha [4], e 9, 2 entram. Retire 2 nós, linha [9, 2], e 6, 8, 5 entram. Retire 3, linha [6, 8, 5], e 3 entra. Retire 1, linha [3], e a fila fica vazia.

Cada nó entra e sai da fila uma vez, então o tempo é O(n). A fila contém no máximo aproximadamente um nível, até 16384 nós no nível mais profundo de uma árvore completa de profundidade 14. Use uma fila de verdade ou um índice de início: retirar o primeiro elemento de uma lista de array simples desloca todos os elementos seguintes em muitas linguagens.

Algoritmo

Coloque o índice 0 da raiz em uma fila.
Enquanto a fila não estiver vazia, leia seu tamanho s e comece uma linha vazia.
Retire s índices. Para cada índice i, acrescente tree[i] à linha.
Adicione 2i+1 e, em seguida, 2i+2 à fila quando o índice estiver dentro do array e não contiver -1.
Acrescente a linha à resposta e comece a próxima rodada.

from collections import deque


def levelOrder(tree):
    n = len(tree)
    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(tree[i])
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and tree[child] != -1:
                    queue.append(child)
        levels.append(row)
    return levels

Armadilhas e casos extremos

A travessia em si é curta. Os bugs estão nos limites dos níveis e nos espaços vazios.

Ler o tamanho da fila enquanto você ainda está esvaziando-a. Em um loop como while (j < queue.length), o tamanho aumenta à medida que os filhos são adicionados, então o próximo nível acaba entrando na linha atual. Leia o tamanho uma vez, antes de a rodada começar.
Adicionar o filho da direita antes do da esquerda. Assim, todos os níveis ficam da direita para a esquerda. O mesmo vale para uma busca em profundidade que visita primeiro a subárvore da direita.
Tratar -1 como um valor. Um espaço vazio não é um nó, então nunca entra em uma linha nem na fila.
Esquecer a verificação dos limites. Os filhos dos nós mais profundos podem ficar além do fim do array, então verifique child < n antes de ler tree[child].
Retornar níveis vazios. As entradas -1 finais não contêm nós, então a resposta para [7, -1, -1] é [[7]], não [[7], []].

Perguntas frequentes4

Qual é a complexidade de tempo da travessia em nível de uma árvore binária?

Tanto a solução em largura quanto a solução em profundidade visitam cada nó uma vez, então executam em tempo O(n) para n nós. A própria resposta contém n valores, então o espaço é O(n). Além disso, a fila contém, no máximo, aproximadamente a quantidade de nós do nível mais largo, e a recursão, no máximo, a altura da árvore.

Como saber onde um nível termina em uma busca em largura?

Leia o tamanho da fila no início de cada rodada. Nesse momento, a fila contém exatamente os nós de um nível, então retirar essa quantidade de nós remove o nível e nada mais. Duas outras maneiras também funcionam: manter o nível atual e o próximo nível em duas listas separadas ou inserir um marcador após cada nível.

É possível fazer uma travessia em ordem por nível com busca em profundidade?

Sim. Passe a cada nó sua profundidade e acrescente seu valor à lista correspondente a essa profundidade. Desde que a travessia visite a subárvore esquerda antes da direita, todas as listas ficam em ordem da esquerda para a direita. Também é O(n); a busca em largura se encaixa melhor, pois produz os níveis em ordem.

A matriz já está armazenada nível por nível. Que tal lê-la em fatias?

Para esse formato, funciona assim: o nível d ocupa os índices 2^d-1 a 2^(d+1)-2, então você pode coletar os valores não vazios de cada intervalo e parar no primeiro intervalo sem nenhum. Em uma entrevista, porém, a árvore geralmente vem como objetos de nós com ponteiros para a esquerda e para a direita, sem índices para fatiar. A travessia baseada em fila é o que se aplica a esse formato e a variantes como a ordem em zigue-zague ou a visualização do lado direito.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado

[[4], [9, 2], [6, 8, 5], [3]]