Boundary Traversal of Binary Tree

Q: Qual é a complexidade de tempo da travessia do contorno?

O(n) . Os dois percursos pelas bordas seguem um caminho cada, e o percurso pelas folhas visita cada nó uma vez. O espaço extra é O(h) para a recursão ou a pilha.

MédioPercurso em árvores

+10

O array root armazena uma árvore binária em ordem por níveis: a raiz no índice 0, os filhos do índice i em 2i+1 (à esquerda) e 2i+2 (à direita), -1 para uma posição vazia e, possivelmente, entradas extras de -1 no final. Uma folha é um nó sem filhos.

Retorne o contorno no sentido anti-horário a partir da raiz:

A raiz.
O contorno esquerdo, de cima para baixo: a partir do filho esquerdo da raiz, avance para o filho esquerdo, se houver; caso contrário, para o filho direito. Pare antes de uma folha.
Todas as folhas, da esquerda para a direita.
O contorno direito, de baixo para cima: o espelho do contorno esquerdo, a partir do filho direito da raiz.

Nenhum nó é listado duas vezes, então uma árvore com um único nó fornece apenas sua raiz.

Função

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

rootinteger-array: a árvore binária em ordem por nível, com -1 para uma posição vazia
Retornainteger-array: os valores de fronteira, no sentido anti-horário a partir da raiz

Restrições

1 ≤ root.length ≤ 32767
Cada root[i] é -1 ou um valor com 0 ≤ root[i] ≤ 10⁵.
root[0] nunca é -1, então a árvore tem pelo menos um nó.
O array pode terminar com entradas extras -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.
Os valores dos nós são distintos.

Exemplos

Entrada: root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]
Saída: [7, 3, 1, 4, 6, 8, 9]
Explicação: Depois da raiz 7, o limite esquerdo é 3: seu filho 1 é uma folha. As folhas são 1, 4, 6, 8. O limite direito é 9, acima da folha 8.

Entrada: root = [10, 4, -1, -1, 6, -1, -1, -1, -1, 5, 8]
Saída: [10, 4, 6, 5, 8]
Explicação: 4 não tem filho à esquerda, então o limite esquerdo passa para 6 e, em seguida, para na folha 5. As folhas 5, 8 vêm em seguida. A raiz não tem filho à direita.

Para ir além

Como você listaria o contorno no sentido horário: a raiz, a borda direita de cima para baixo, as folhas da direita para a esquerda e, então, a borda esquerda de baixo para cima?

Dicas

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

0 de 3 abertas

Solução

A resposta une quatro partes: a raiz, um caminho descendo pela borda esquerda, as folhas da esquerda para a direita e um caminho descendo pela borda direita, lido de trás para frente. Nas junções, uma folha que termina uma borda e uma raiz que é uma folha devem ser listadas uma única vez cada.

Percorra as três partes separadamente

Intuição

Cada borda é um caminho: a partir do filho da raiz, liste os nós até que o próximo seja uma folha, que é listada na parte das folhas. Uma travessia em pré-ordem que percorre a esquerda antes da direita encontra as folhas na ordem da esquerda para a direita, porque todos os nós de uma subárvore esquerda ficam à esquerda da subárvore direita, independentemente da profundidade. Colete a borda direita de cima para baixo e acrescente-a invertida.

As bordas percorrem um caminho cada, e a travessia das folhas visita cada nó uma vez: tempo O(n), com recursão de h níveis de profundidade.

Algoritmo

Comece pela raiz; se ela for uma folha, retorne-a.
A partir do índice 1, enquanto o nó existir e não for uma folha, adicione-o e avance para o filho esquerdo ou, se não houver um, para o filho direito.
Percorra em pré-ordem, começando pela esquerda, a partir dos índices 1 e 2, adicionando todas as folhas.
A partir do índice 2, faça o mesmo que na etapa 2, dando preferência aos filhos direitos e coletando os nós.
Adicione os nós coletados na ordem inversa.

def boundaryTraversal(root):
    n = len(root)

    def real(i):
        return i < n and root[i] != -1

    def is_leaf(i):
        return not real(2 * i + 1) and not real(2 * i + 2)

    result = [root[0]]
    if is_leaf(0):
        return result

    # 1. The left boundary, top-down, stopping before its leaf.
    i = 1
    while real(i) and not is_leaf(i):
        result.append(root[i])
        i = 2 * i + 1 if real(2 * i + 1) else 2 * i + 2

    # 2. Every leaf: a pre-order walk meets them from left to right.
    def add_leaves(i):
        if not real(i):
            return
        if is_leaf(i):
            result.append(root[i])
            return
        add_leaves(2 * i + 1)
        add_leaves(2 * i + 2)

    add_leaves(1)
    add_leaves(2)

    # 3. The right boundary, collected top-down and added bottom-up.
    right = []
    i = 2
    while real(i) and not is_leaf(i):
        right.append(root[i])
        i = 2 * i + 2 if real(2 * i + 2) else 2 * i + 1
    result.extend(reversed(right))
    return result

Uma passagem em pré-ordem com sinalizadores de aresta

Intuição

Reúna as caminhadas em uma única passagem em pré-ordem usando uma pilha, atribuindo uma sinalização a cada nó: 1 na borda esquerda, 2 na borda direita, 0 no interior. Os filhos da raiz começam com 1 e 2. Um nó de borda passa sua sinalização ao filho do seu lado ou ao seu único filho; todos os demais filhos recebem 0. No segundo exemplo, o 1 passa de 4 para 6 e depois para 5.

À medida que os nós saem da pilha, acrescente todas as folhas e todos os nós que não são folhas sinalizados com 1; reúna os nós que não são folhas sinalizados com 2 e acrescente-os invertidos ao final. A pré-ordem alcança todos os nós da borda esquerda antes de qualquer folha, porque a borda vira à direita somente onde nada fica à sua esquerda.

Algoritmo

Comece pela raiz. Empilhe seu filho direito com a flag 2 e, em seguida, seu filho esquerdo com a flag 1.
Desempilhe um nó. Acrescente-o se for uma folha ou tiver a flag 1; adicione à lista da direita um nó que não seja folha e tenha a flag 2.
Empilhe seu filho direito e, em seguida, seu filho esquerdo, cada um com a flag que a regra lhe atribui.
Quando a pilha estiver vazia, acrescente a lista da direita invertida.

def boundaryTraversal(root):
    n = len(root)

    def real(i):
        return i < n and root[i] != -1

    result = [root[0]]
    right = []  # the right boundary, top-down; it goes on the end reversed
    # Each entry is (index, edge): 1 = left boundary, 2 = right boundary, 0 = inside.
    stack = []
    if real(2):
        stack.append((2, 2))
    if real(1):
        stack.append((1, 1))
    while stack:
        i, edge = stack.pop()
        has_left, has_right = real(2 * i + 1), real(2 * i + 2)
        if not has_left and not has_right:
            result.append(root[i])  # a leaf; pre-order meets them left to right
        elif edge == 1:
            result.append(root[i])  # the left boundary, top-down
        elif edge == 2:
            right.append(root[i])
        # An edge passes to the child on its own side, or to an only child.
        # The right child goes on the stack first, so the left one comes out first.
        if has_right:
            stack.append((2 * i + 2, edge if edge == 2 or not has_left else 0))
        if has_left:
            stack.append((2 * i + 1, edge if edge == 1 or not has_right else 0))
    result.extend(reversed(right))
    return result

Armadilhas e casos extremos

Listar um nó duas vezes. Um percurso pelas arestas que não para antes da folha lista 1 duas vezes no exemplo 1, e uma árvore com um único nó não deve listar sua raiz novamente como folha.
Considerar o primeiro nó de cada nível como o limite esquerdo. Se o filho esquerdo da raiz for uma folha e a subárvore direita for mais profunda, os níveis mais profundos começam com nós da subárvore direita, mas o limite esquerdo está vazio.
Seguir apenas os filhos esquerdos. No exemplo 2, o limite deve ir de 4 ao seu filho direito 6.
Coletar as folhas nível por nível. Assim, o exemplo 1 resulta em 1, 8, 4, 6.
Em Lua e R, mantenha os índices dos nós baseados em 0 para a aritmética 2i+1 e leia root[i + 1].

Perguntas frequentes3

O que é a travessia do contorno de uma árvore binária?

Ele lista o contorno da árvore no sentido anti-horário: a raiz, a borda esquerda de cima para baixo, as folhas da esquerda para a direita e a borda direita de baixo para cima. As bordas não incluem suas folhas, então nenhum nó aparece duas vezes.

Qual é a complexidade de tempo da travessia do contorno?

O(n). Os dois percursos pelas bordas seguem um caminho cada, e o percurso pelas folhas visita cada nó uma vez. O espaço extra é O(h) para a recursão ou a pilha.

O limite à esquerda sempre segue os filhos à esquerda?

Não. Ele se move para o filho esquerdo quando há um e para o filho direito caso contrário: o caminho mais externo que você vê pela esquerda. Se a raiz não tiver filho esquerdo, o limite esquerdo estará vazio.

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

Teste #1

Teste #2

Teste #3

Argumento

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

Saída Esperada

[7, 3, 1, 4, 6, 8, 9]