Binary Tree Right Side View

Q: Qual é a complexidade de tempo e espaço da visualização do lado direito de uma árvore binária?

O tempo é O(n) para n nós, e nenhuma solução pode pular nós, pois o nó mais à direita de um nível pode estar em qualquer lugar. O espaço é O(w) para a fila, em que w é o nível mais largo, ou O(h) para a travessia começando pela direita em uma árvore com h níveis.

MédioPercurso em árvores Fila

+10

O array root contém uma árvore binária. 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 entradas extras -1 podem aparecer no final.

Observe a árvore pelo lado direito. Cada nível mostra exatamente um nó, o que está mais à direita, e oculta os demais. Liste esses valores do nível da raiz até o nível mais profundo.

Função

rightSideView(root: integer-array) → integer-array

rootinteger-array: a árvore na ordem de heap, com -1 para uma posição vazia
Retornainteger-array: o valor mais à direita de cada nível, começando pelo nível superior

Restrições

1 ≤ root.length ≤ 32767
Cada root[i] é -1 ou um valor com 0 ≤ root[i] ≤ 10⁴.
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 -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, 7, 4, -1, 1, -1, 3]
Saída: [5, 9, 1, 3]
Explicação: Pela direita, você vê 5, 9 e 1 (índice 6). O quarto nível contém apenas 3, no índice 8, abaixo de 7, na subárvore esquerda. Nada à direita chega tão fundo, então 3 fica visível.

Entrada: root = [6, 0, -1, 8, -1, -1, -1]
Saída: [6, 0, 8]
Explicação: A árvore é uma cadeia de filhos à esquerda: 6, 0, 8. Cada nível contém um nó, então você vê os três, embora nenhum deles seja um filho à direita.

Entrada: root = [42]
Saída: [42]
Explicação: Um array de comprimento 1: a raiz 42 não tem nenhum espaço para filhos, e a visualização é esse único valor.

Para ir além

Como você obteria a vista do lado direito de uma árvore em que cada nó pode ter qualquer número de filhos, armazenados em uma lista da esquerda para a direita?

Dicas

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

0 de 3 abertas

Solução

Você vê o nó mais à direita de cada nível, e ele não precisa ser um filho à direita: o último valor do exemplo 1 fica na subárvore esquerda. Uma busca em largura faz desse nó o último de cada rodada; uma travessia em profundidade que começa pela direita o encontra antes de qualquer outro nó do mesmo nível.

Busca em largura, último nó de cada nível

Intuição

Processe a árvore um nível por rodada. Quando uma rodada começa, a fila contém exatamente um nível, da esquerda para a direita; assim, o último índice que você desenfileira na rodada corresponde ao nó mais à direita desse nível, e seu valor é adicionado à resposta.

No exemplo 1, as rodadas são [5], [2, 9], [7, 4, 1] e [3], e seus últimos elementos resultam em 5, 9, 1, 3. O que importa é o nível, não o lado: 3 está na subárvore esquerda, mas está sozinho em seu nível.

Cada índice é enfileirado e desenfileirado uma vez, então o tempo é O(n). A fila cresce até a largura do nível mais largo, O(n) no pior caso.

Algoritmo

Enfileire o índice 0 da raiz.
Comece uma rodada salvando o tamanho da fila s.
Desenfileire s índices. Para cada índice i, enfileire 2i+1 e, em seguida, 2i+2, se estiverem dentro dos limites do comprimento do array e não forem -1.
Acrescente o valor do último índice desenfileirado na rodada.
Repita até que a fila esteja vazia e, então, retorne a resposta.

from collections import deque


def rightSideView(root):
    n = len(root)
    view = []
    queue = deque([0])  # node indexes; the root is never empty
    while queue:
        size = len(queue)  # exactly the nodes of the current level
        for j in range(size):
            i = queue.popleft()
            if j == size - 1:
                view.append(root[i])  # the last node of this level
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and root[child] != -1:
                    queue.append(child)
    return view

Busca em profundidade, primeiro o filho à direita

Intuição

Percorra a árvore em profundidade, tentando o filho da direita antes do da esquerda, e carregue a profundidade, começando em 0 na raiz. Na primeira vez que a busca alcançar a profundidade d, a resposta terá exatamente d valores. Acrescente o valor do nó nesse momento e ignore todos os nós posteriores nesse nível.

Esse primeiro nó é o mais à direita: sempre que dois caminhos para um nível se separam, a busca segue pelo ramo da direita até o fim antes de voltar e seguir pelo da esquerda. No exemplo 1, a busca visita 5, 9, 1, 2, 4, 7, 3: ela ignora 2, 4 e 7, cujas profundidades já têm um valor, e acrescenta 3.

Cada nó é visitado uma vez, em tempo O(n), com uma chamada por nível na pilha, no máximo 14.

Algoritmo

Comece com uma resposta vazia e a raiz na profundidade 0.
Pule um índice que esteja além do fim do array ou contenha -1.
Quando o comprimento da resposta for igual à profundidade, acrescente o valor: o percurso chegou a um novo nível, e chegou a ele pela direita.
Recorra primeiro ao filho à direita 2i+2 e, em seguida, ao filho à esquerda 2i+1, cada um um nível mais profundo.
Retorne a resposta.

def rightSideView(root):
    n = len(root)
    view = []

    def visit(i, depth):
        if i >= n or root[i] == -1:
            return
        if depth == len(view):  # the first node met on this level
            view.append(root[i])
        # Right before left, so the rightmost node of every level comes first.
        visit(2 * i + 2, depth + 1)
        visit(2 * i + 1, depth + 1)

    visit(0, 0)
    return view

Armadilhas e casos extremos

Seguir apenas os filhos direitos a partir da raiz. O exemplo 1 resulta em [5, 9, 1] e não inclui 3; o exemplo 2 resulta em [6].
Ler o último espaço de cada nível, root[2^(d+1)-2]. No exemplo 2, o índice 6 contém -1; o nó visível é 8 no índice 3.
Ignorar a verificação de comprimento em uma posição de filho. No exemplo 1, 3 é a última entrada, então suas posições de filho 17 e 18 não existem.
Enfileirar primeiro o filho direito e manter o último nó de cada rodada. Isso coleta a visão esquerda, [5, 2, 7, 3].
Permitir que nós posteriores sobrescrevam os anteriores na travessia da direita para a esquerda, o que também resulta na visão esquerda.

Perguntas frequentes3

Qual é a complexidade de tempo e espaço da visualização do lado direito de uma árvore binária?

O tempo é O(n) para n nós, e nenhuma solução pode pular nós, pois o nó mais à direita de um nível pode estar em qualquer lugar. O espaço é O(w) para a fila, em que w é o nível mais largo, ou O(h) para a travessia começando pela direita em uma árvore com h níveis.

Uma busca em profundidade priorizando a esquerda consegue resolver isso?

Sim, se você sobrescrever em vez de manter o primeiro valor. Uma travessia da esquerda para a direita encontra os nós de cada nível da esquerda para a direita, então armazene o valor de cada nó em sua profundidade e deixe os nós posteriores substituírem os anteriores. Cada profundidade termina com seu valor mais à direita. Ainda é O(n), mas escreve uma vez por nó.

Devo usar busca em largura ou busca em profundidade aqui?

Ambos são lineares. A busca em largura segue a definição, um nível por rodada. A busca em profundidade mantém apenas o caminho atual, o que economiza memória em uma árvore larga, e sua forma recursiva tem algumas linhas a menos.

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

Teste #1

Teste #2

Teste #3

Argumento

root = [5, 2, 9, 7, 4, -1, 1, -1, 3]

Saída Esperada

[5, 9, 1, 3]