Vertical Order Traversal of a Binary Tree

DifícilPercurso em árvores Ordenação Hashing

+10

Uma árvore binária é armazenada no array root na ordem de heap: a raiz está no índice 0, os filhos do índice i estão em 2*i+1 (à esquerda) e 2*i+2 (à direita), -1 indica um espaço vazio, e o array pode terminar com entradas extras -1.

A raiz está na coluna 0; um filho à esquerda fica uma coluna à esquerda de seu pai, e um filho à direita fica uma coluna à direita. Retorne uma lista por coluna, da esquerda para a direita. Dentro de uma coluna, liste os nós de cima para baixo e, entre os nós que compartilham uma coluna e uma profundidade, em ordem crescente de valor.

Função

verticalTraversal(root: integer-array) → integer-2d-array

rootinteger-array: a árvore em ordem de heap, com -1 para uma posição vazia
Retornainteger-2d-array: uma lista de valores por coluna, começando pela coluna mais à esquerda, cada uma de cima para baixo

Restrições

1 ≤ root.length ≤ 32767
Cada root[i] é -1 ou um valor com 0 ≤ root[i] ≤ 5000, e nenhum valor aparece duas vezes.
root[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 árvore tem no máximo 14 níveis.

Exemplos

Entrada: root = [5, 2, 9, 4, 7, 1, 6]
Saída: [[4], [2], [5, 1, 7], [9], [6]]
Explicação: A coluna 0 contém a raiz 5, depois 7 e 1 dois níveis abaixo. Esses dois compartilham a coluna e a profundidade, então 1 vem antes de 7, embora 7 esteja mais à esquerda.

Entrada: root = [1, 2, 3, -1, 4, -1, -1, -1, -1, 5]
Saída: [[2, 5], [1, 4], [3]]
Explicação: A coluna -1 contém 2 na profundidade 1 e 5 na profundidade 3 (o filho esquerdo de 4). A coluna 0 contém a raiz 1 e 4 no índice 4. A coluna 1 contém apenas 3.

Entrada: root = [6, -1, -1]
Saída: [[6]]
Explicação: 6 não tem filhos, então a resposta tem uma única coluna, [6].

Para ir além

Cada valor é, no máximo, 5000. Você consegue usar isso para dispensar a ordenação por comparação e concluir em O(n + 5000) tempo?

Solução

Cada nó tem três chaves: coluna, profundidade e valor. A resposta são os nós ordenados por essas chaves, uma lista por coluna. Em caso de empate na coluna e na profundidade, a ordem é determinada pelo valor, não pela ordem da esquerda para a direita em que uma travessia os encontra; portanto, você precisa ordenar: todos os nós de uma vez ou cada nível de uma busca em largura.

Registre cada nó e, em seguida, ordene

Intuição

Visite cada nó uma vez, em qualquer ordem, e registre a tripla (coluna, profundidade, valor). Um passo até um filho adiciona 1 à profundidade e move a coluna 1 para a esquerda ou para a direita. Em seguida, ordene as triplas por coluna, profundidade e valor. Agora, os nós de cada coluna ficam juntos, na ordem necessária. Percorra a lista ordenada e inicie uma nova lista interna sempre que a coluna mudar.

No exemplo 1, as triplas da coluna 0 ficam ordenadas assim: (0, 0, 5), (0, 2, 1), (0, 2, 7). A ordenação, O(n log n), domina o percurso de O(n), e as triplas ocupam O(n) de espaço.

Algoritmo

Empilhe (índice 0, coluna 0, profundidade 0) em uma pilha.
Desempilhe um nó, registre (coluna, profundidade, valor) e empilhe cada filho real com coluna col-1 ou col+1 e profundidade depth+1.
Quando a pilha estiver vazia, ordene as tuplas por coluna, depois por profundidade e, em seguida, por valor.
Percorra-as, iniciando uma nova lista sempre que a coluna mudar.

def verticalTraversal(root):
    n = len(root)
    entries = []  # (column, depth, value) for every node
    stack = [(0, 0, 0)]  # (node index, column, depth); the root is never empty
    while stack:
        i, col, depth = stack.pop()
        entries.append((col, depth, root[i]))
        for child, child_col in ((2 * i + 1, col - 1), (2 * i + 2, col + 1)):
            if child < n and root[child] != -1:
                stack.append((child, child_col, depth + 1))
    # Column, then depth, then value: exactly the order of the answer.
    entries.sort()
    result = []
    for k, (col, depth, value) in enumerate(entries):
        if k == 0 or col != entries[k - 1][0]:
            result.append([])  # a new column starts
        result[-1].append(value)
    return result

Nível por nível, classifique dentro de cada nível

Intuição

Uma busca em largura processa um nível por vez. Se cada nó acrescentar seu valor à lista de sua coluna quando for processado, todas as listas já estarão ordenadas de cima para baixo, então não é necessário ordenar por profundidade. Empates ocorrem apenas dentro de um mesmo nível, então ordene cada nível por coluna e, em seguida, por valor, antes de processá-lo.

No exemplo 1, o nível 2 chega como 4, 7, 1, 6 nas colunas -2, 0, 0, 2 e é ordenado como 4, 1, 7, 6, então a coluna 0 se torna [5, 1, 7]. As colunas ocupadas formam um intervalo contínuo, então basta acompanhar a menor e a maior.

Ordenar um nível de m nós custa O(m log m). No pior caso, a complexidade ainda é O(n log n), porque o último nível de uma árvore completa contém cerca de metade dos nós. O espaço é O(n).

Algoritmo

Comece com um nível que contém (índice 0, coluna 0).
Ordene o nível por coluna e, em seguida, por valor.
Nessa ordem, anexe cada valor à lista de sua coluna e reúna seus filhos reais, com as colunas col-1 e col+1, no próximo nível.
Repita até que um nível esteja vazio, acompanhando a menor e a maior coluna.
Retorne as listas da menor coluna até a maior.

def verticalTraversal(root):
    n = len(root)
    columns = {}  # column -> its values, top to bottom
    level = [(0, 0)]  # (node index, column) of every node on the current level
    while level:
        # Every node here has the same depth: order them by column, then value.
        level.sort(key=lambda node: (node[1], root[node[0]]))
        next_level = []
        for i, col in level:
            columns.setdefault(col, []).append(root[i])
            for child, child_col in ((2 * i + 1, col - 1), (2 * i + 2, col + 1)):
                if child < n and root[child] != -1:
                    next_level.append((child, child_col))
        level = next_level
    # The columns that hold a node form one unbroken range.
    return [columns[col] for col in range(min(columns), max(columns) + 1)]

Armadilhas e casos extremos

Manter empates na ordem da esquerda para a direita. Uma busca em largura sem a ordenação por nível resulta em [5, 7, 1] para a coluna 0 do exemplo 1, não em [5, 1, 7].
Anexar valores durante uma caminhada em profundidade sem ordenação. Em [1, 2, 3, -1, 4, -1, -1, -1, -1, -1, 5], uma caminhada priorizando a esquerda anexa 5 (profundidade 3) à coluna 1 antes de 3 (profundidade 1).
Ordenar por coluna e valor, mas não por profundidade. A coluna 0 do exemplo 1 passa a ser [1, 5, 7].
Usar strings como chave das colunas. Ordenando como texto, "-1" vem antes de "-2", então as colunas à esquerda de 0 ficam na ordem errada.

Perguntas frequentes3

Qual é a complexidade de tempo da travessia em ordem vertical de uma árvore binária?

Ordenar todos os nós por coluna, profundidade e valor custa O(n log n) e domina a travessia O(n). Ordenar nível por nível tem o mesmo caso pior, porque o último nível de uma árvore completa contém cerca de metade dos nós. O espaço é O(n).

É possível fazer a travessia em ordem vertical sem ordenar?

Somente se os empates seguirem a ordem da esquerda para a direita. Então, uma busca em largura que adiciona cada valor à lista de sua coluna fornece a resposta em O(n). Se os empates forem ordenados por valor, será necessário algum tipo de ordenação, mas apenas dentro de um nível, pois somente nós em um mesmo nível podem empatar.

Como a travessia em ordem vertical se relaciona com a visão de cima e a visão de baixo?

Os três agrupam os nós pelas mesmas colunas. A vista superior mantém o nó mais raso de cada coluna, e a vista inferior, o mais profundo. A travessia em ordem vertical mantém todos os nós e, quando vários compartilham o mesmo nível, ordena-os por valor, enquanto as vistas selecionam os nós pela posição.

def verticalTraversal(root):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

root = [5, 2, 9, 4, 7, 1, 6]

Saída Esperada

[[4], [2], [5, 1, 7], [9], [6]]