Left View of Binary Tree

+10

Você recebe uma árvore binária como o 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), e -1 marca uma posição vazia. O array pode terminar com entradas extras -1.

Fique à esquerda da árvore. Em cada nível, você vê um nó, o mais à esquerda; o restante do nível fica escondido atrás dele. Retorne os valores que você vê, do nível superior para baixo.

Função

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

rootinteger-array: a árvore em ordem de heap, com -1 para uma posição vazia
Retornainteger-array: o valor mais à esquerda 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ó.
O 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 árvore tem no máximo 14 níveis.

Exemplos

Entrada: root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]
Saída: [3, 8, 6, 1]
Explicação: 8 é uma folha, então o terceiro e o quarto níveis contêm apenas 6 (índice 6) e 1 (índice 13), ambos sob o filho direito 5. Você os vê mesmo assim: [3, 8, 6, 1].

Entrada: root = [10, -1, -1]
Saída: [10]
Explicação: Os índices 1 e 2 contêm -1, então 10 não tem filhos e a visualização contém apenas a raiz.

Entrada: root = [1, 2, 3, 4, 5, 6, 7]
Saída: [1, 2, 4]
Explicação: Uma árvore completa de três níveis. As posições mais à esquerda dos níveis são os índices 0, 1 e 3, que contêm 1, 2 e 4.

Para ir além

Nível d preenche os índices de 2^d-1 a 2^(d+1)-2. Você consegue montar a visualização percorrendo esses intervalos, sem fila nem recursão? Qual é o custo disso em um array preenchido?

Solução

Seguir os filhos à esquerda a partir da raiz falha quando a subárvore esquerda é mais curta: no primeiro exemplo, os níveis inferiores são vistos através da subárvore direita. Você quer o primeiro nó de cada nível. A busca em largura percorre cada nível da esquerda para a direita; uma busca em profundidade que segue primeiro à esquerda encontra primeiro o nó mais à esquerda de cada nível.

Busca em largura, primeiro nó de cada nível

Intuição

Uma fila processada em rodadas fornece os níveis um de cada vez. No início de uma rodada, a fila contém exatamente um nível, da esquerda para a direita, porque cada filho adicionado durante a rodada fica atrás dele. Remova essa quantidade de índices, enfileire os filhos de cada um começando pela esquerda e mantenha o primeiro valor.

No primeiro exemplo, as rodadas são [3], [8, 5], [6] e [1], e elas mantêm 3, 8, 6 e 1. O 8 não adiciona nada, porque as posições de seus filhos, 3 e 4, contêm -1.

Cada nó entra e sai da fila uma vez: tempo O(n). A fila contém um nível inteiro, até 8192 índices em uma árvore completa de 14 níveis.

Algoritmo

Comece uma fila contendo o índice 0 e uma resposta vazia.
Enquanto a fila não estiver vazia, considere s como seu tamanho e remova s índices. Acrescente o valor do primeiro.
Para cada índice removido i, enfileire 2i+1 e depois 2i+2, ignorando índices além do final e entradas iguais a -1.

from collections import deque


def leftView(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 == 0:
                view.append(root[i])  # the first 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

Em profundidade, primeiro o filho à esquerda

Intuição

Percorra a árvore em profundidade, visitando a subárvore esquerda antes da direita, e passe a profundidade de cada nó. O primeiro nó alcançado pela travessia na profundidade d é o mais à esquerda no nível d. Considere o nó mais à esquerda x de um nível e qualquer nó y à sua direita: no último nó em que seus caminhos se encontram, x segue para a esquerda e y para a direita, e a travessia termina o ramo esquerdo antes de seguir para a direita.

A travessia desce um nível por vez, então, ao alcançar pela primeira vez a profundidade d, a resposta contém exatamente d valores. Registre um nó quando d for igual ao comprimento da resposta; não é necessário manter um conjunto de profundidades visitadas.

Cada nó é visitado uma vez, tempo O(n), e a memória mantém uma chamada por nível, no máximo 14 neste caso. A versão em R mantém sua própria pilha e empilha o filho direito antes do esquerdo.

Algoritmo

Crie uma resposta vazia e chame visit(0, 0).
Em visit(i, d), retorne imediatamente se i estiver fora do array ou se root[i] for -1.
Se d for igual ao comprimento da resposta, a caminhada alcançou o nível d pela primeira vez: acrescente root[i].
Chame visit(2i+1, d+1) e, em seguida, visit(2i+2, d+1).
Retorne a resposta assim que a primeira chamada terminar.

def leftView(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])
        # Left before right, so the leftmost node of every level comes first.
        visit(2 * i + 1, depth + 1)
        visit(2 * i + 2, depth + 1)

    visit(0, 0)
    return view

Armadilhas e casos extremos

Seguir apenas os filhos à esquerda a partir da raiz. No primeiro exemplo, isso para em 8 e deixa de encontrar 6 e 1.
Ler o primeiro elemento de cada nível, root[2^d-1]. No primeiro exemplo, o primeiro elemento do terceiro nível, índice 3, contém -1, enquanto seu único nó está no índice 6.
Visitar primeiro o filho à direita na busca em profundidade. O primeiro nó encontrado em cada nível será então o mais à direita.
Ler um filho sem verificar os limites. O 1 no índice 13 tem posições de filhos 27 e 28, além do fim do array de 14 elementos.

Perguntas frequentes3

A visualização à esquerda é igual ao limite esquerdo de uma árvore?

Não. O limite esquerdo é um caminho: começa no filho esquerdo da raiz, segue para a esquerda quando pode, caso contrário, para a direita, e para antes de uma folha. A vista esquerda pega um nó por nível de qualquer ramo. No primeiro exemplo, o limite está vazio, já que 8 é uma folha, mas a vista mostra 8, 6 e 1.

Qual é a complexidade de tempo e espaço da vista esquerda?

Ambas as soluções percorrem cada nó uma vez, então o tempo é O(n). A fila da busca em largura contém um nível inteiro, cerca de metade dos nós de uma árvore completa. A busca primeiro à esquerda mantém uma chamada por nível, O(h) para h níveis.

Como você altera a solução para obter a visualização correta?

Na versão em largura primeiro, mantenha o último valor de cada rodada em vez do primeiro. Na versão em profundidade primeiro, visite o filho direito antes do esquerdo; assim, o primeiro nó que a travessia alcança em cada nível é o mais à direita.

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

Teste #1

Teste #2

Teste #3

Argumento

root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]

Saída Esperada

[3, 8, 6, 1]