Binary Tree Level Order Traversal

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

As duas soluções visitam cada nó uma vez: tempo O(n) para n nós. A resposta contém n valores, então o espaço é O(n) . Além disso, a fila comporta aproximadamente o nível mais largo, e a recursão, a altura da árvore.

Q: Como você sabe onde um nível termina em uma busca em largura?

Leia o tamanho da fila no início de cada rodada e processe exatamente esse número de nós. Duas outras maneiras também funcionam: mantenha o nível atual e o próximo nível em duas listas separadas ou insira um marcador na fila após cada nível.

Q: O array já está armazenado nível por nível. Por que não lê-lo em partes?

Para esse formato, funciona assim: o nível d , com a raiz em 0, preenche os índices 2^d-1 a 2^(d+1)-2 ; portanto, colete os valores não vazios de cada intervalo até que um intervalo não tenha nenhum. Em entrevistas, geralmente são passados objetos de nó com ponteiros, e apenas a fila é aproveitada nesse formato.

MédioPercurso em árvores Fila

+10

O array tree armazena uma árvore binária. 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 marca uma posição vazia e entradas extras -1 podem aparecer no final.

Retorne os valores dos nós nível por nível: uma lista por nível, da raiz até o nível mais profundo, cada uma com seus valores da esquerda para a direita.

Função

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

treeinteger-array: a árvore na 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, cada uma da esquerda para a direita

Restrições

1 ≤ tree.length ≤ 32767
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 extras de -1 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: O índice 3 está vazio, então 9 tem apenas um filho à direita, 6. O terceiro nível contém 6, 8, 5, e o 3 no índice 9, abaixo de 6, está 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 nó único 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.

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 deve resultar em sua própria lista da esquerda para a direita. Uma busca em largura com uma fila visita os nós nessa ordem e, no início de cada rodada, a fila contém exatamente um nível, então seu tamanho indica quantos nós devem ser processados. Uma busca em profundidade que acompanha a profundidade de cada nó também funciona.

Busca em profundidade, agrupada por profundidade

Intuição

Percorra a árvore em profundidade, passando a profundidade de cada nó: 0 para a raiz; e mantenha uma lista por profundidade. Um nó na profundidade d acrescenta seu valor à lista d, iniciando essa lista se for o primeiro nó encontrado nesse nível.

Cada lista fica ordenada da esquerda para a direita, pois a travessia termina a subárvore esquerda de um nó antes de entrar na direita. Entre dois nós no mesmo nível, aquele cujo caminho vira à esquerda no ponto em que os caminhos se separam é alcançado primeiro. No exemplo 1, a ordem de visita 4, 9, 6, 3, 2, 8, 5 preenche [4], [9, 2], [6, 8, 5], [3].

Cada nó é visitado uma vez: tempo O(n), com recursão tão profunda quanto a árvore, no máximo 14 níveis.

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

Retire um nó da fila e coloque seus filhos nela, começando pela esquerda. O nível d+1 só entra quando o nível d sai, então os nós saem nível por nível, da esquerda para a direita.

Para dividir esse fluxo em níveis, leia o tamanho da fila no início de uma rodada. O nível anterior já saiu e nenhum nó do próximo chegou, então a fila contém exatamente o nível atual. Retire essa quantidade de nós para formar uma linha; seus filhos aguardam a próxima rodada. No exemplo 1, as rodadas retiram 1, 2, 3 e 1 nós.

Cada nó entra e sai da fila uma vez: tempo O(n). A fila comporta aproximadamente um nível, no máximo 8.192 nós no nível mais profundo de uma árvore completa de 14 níveis.

Algoritmo

Coloque o índice da raiz 0 em uma fila.
Enquanto a fila não estiver vazia, leia seu tamanho s e inicie 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 inicie 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

Ler o tamanho da fila enquanto você a esvazia. Em while (j < queue.length), o comprimento aumenta conforme os filhos chegam, então o próximo nível acaba entrando na linha atual.
Adicionar o filho direito antes do esquerdo ou visitar primeiro a subárvore direita. O segundo nível do Exemplo 1 passa a ser [2, 9].
Ignorar a verificação do limite child < n. Os filhos dos nós mais profundos ficam além do fim do array.
Remover do início de uma lista de array simples, o que, em muitas linguagens, desloca toda a fila a cada remoção. Use uma fila de verdade ou um índice de início.
Tratar -1 como um nó. Ele nunca entra em uma linha nem na fila: [7, -1, -1] resulta em [[7]], não em [[7], []].

Perguntas frequentes3

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

As duas soluções visitam cada nó uma vez: tempo O(n) para n nós. A resposta contém n valores, então o espaço é O(n). Além disso, a fila comporta aproximadamente o nível mais largo, e a recursão, a altura da árvore.

Como você sabe onde um nível termina em uma busca em largura?

Leia o tamanho da fila no início de cada rodada e processe exatamente esse número de nós. Duas outras maneiras também funcionam: mantenha o nível atual e o próximo nível em duas listas separadas ou insira um marcador na fila após cada nível.

O array já está armazenado nível por nível. Por que não lê-lo em partes?

Para esse formato, funciona assim: o nível d, com a raiz em 0, preenche os índices 2^d-1 a 2^(d+1)-2; portanto, colete os valores não vazios de cada intervalo até que um intervalo não tenha nenhum. Em entrevistas, geralmente são passados objetos de nó com ponteiros, e apenas a fila é aproveitada nesse formato.

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

Teste #1

Teste #2

Teste #3

Argumento

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

Saída Esperada

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