Diameter of Binary Tree

+10

Você recebe uma árvore binária armazenada no array tree em ordem por níveis. 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 indica uma posição vazia, e o array pode terminar com entradas -1 extras. Retorne o diâmetro da árvore: o número de arestas no caminho mais longo entre quaisquer dois nós. O caminho pode passar pela raiz ou permanecer dentro de uma subárvore.

Função

diameterOfBinaryTree(tree: integer-array) → integer

treeinteger-array: a árvore binária em ordem por nível, com -1 para uma posição vazia
Retornainteger: o número de arestas no caminho mais longo entre dois nós

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ó.
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.

Exemplos

Entrada: tree = [8, 3, 6, 1, 4, -1, -1, -1, -1, 7]
Saída: 4
Explicação: O caminho 7, 4, 3, 8, 6 (índices 9, 4, 1, 0, 2) contém cinco nós conectados por quatro arestas. Ele faz uma curva na raiz: três arestas descendo pelo lado esquerdo e uma pelo direito.

Entrada: tree = [2, 5, -1, 1, 9, -1, -1, 3, -1, -1, 4]
Saída: 4
Explicação: O caminho 3, 1, 5, 9, 4 tem quatro arestas e muda de direção no 5 no índice 1. A raiz não tem filho à direita, então um caminho que passa pela raiz tem apenas as três arestas que descem pelo lado esquerdo.

Entrada: tree = [6, -1, -1]
Saída: 0
Explicação: Um único nó não tem arestas. O caminho mais longo é o próprio nó, de comprimento 0.

+12 testes ocultos ao enviar

Para ir além

Como você retornaria o próprio caminho, com os valores dos nós de uma extremidade do diâmetro à outra?

Dicas

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

0 de 3 abertas

Solução

O caminho mais longo não precisa passar pela raiz, então medir os dois lados da raiz não é suficiente. Todo caminho tem um nó mais alto, onde muda de direção: de subida para descida, e o caminho mais longo que muda de direção em um nó é a altura da esquerda mais a altura da direita. Uma única passagem em pós-ordem calcula cada altura de baixo para cima e verifica cada ponto de mudança de direção pelo caminho, em O(n).

Meça cada par de nós

Correta, mas não termina nos maiores testes

Intuição

Primeiro, como percorrer o array. O nó no índice i tem o filho esquerdo em 2*i+1 e o filho direito em 2*i+2, então seu pai fica em (i-1)/2, arredondado para baixo. Uma posição só é válida se seu índice estiver dentro do array e o valor nessa posição não for -1. Em [8, 3, 6, 1, 4, -1, -1, -1, -1, 7], o 7 no índice 9 tem seu pai no índice 4, e esse 4 tem seu pai no índice 1.

O diâmetro é a maior distância entre dois nós, então você pode medir todos os pares. Para obter a distância entre os índices a e b, suba em direção à raiz um passo de cada vez até que eles se encontrem, sempre a partir do índice maior. Um índice maior nunca está em um nível mais alto, então esse passo nunca passa do ponto de encontro. O número de passos é o número de arestas. Para 9 e 2: o 9 sobe até 4 e depois até 1, o 2 sobe até 0, e o 1 sobe até 0. Quatro passos.

Isso está correto, mas é lento. O maior teste é uma árvore completa com 16383 nós, o que resulta em cerca de 1.3 × 10^8 pares, e cada par exige até 26 passos. Bilhões de passos para uma única resposta ultrapassam em muito o limite de tempo.

Algoritmo

Reúna os índices de todos os nós reais.
Para cada par (a, b), defina edges = 0 e repita até a == b: substitua o maior índice por seu pai e adicione 1 a edges.
Mantenha o maior valor de edges que encontrar e retorne-o.

def diameterOfBinaryTree(tree):
    nodes = [i for i, value in enumerate(tree) if value != -1]
    best = 0
    for x in range(len(nodes)):
        for y in range(x + 1, len(nodes)):
            a, b = nodes[x], nodes[y]
            edges = 0
            while a != b:
                # A larger index is never higher up, so climb from it.
                if a > b:
                    a = (a - 1) // 2
                else:
                    b = (b - 1) // 2
                edges += 1
            best = max(best, edges)
    return best

Meça ambas as alturas em cada nó

Intuição

Observe o caminho mais longo a partir do seu nó mais alto, o nó onde ele para de subir e começa a descer. A partir daí, ele desce o máximo possível pelo lado esquerdo e pelo lado direito. Considere que height(c) conta os nós no caminho descendente mais longo a partir de c, sendo 0 para uma posição vazia. Então, o caminho mais longo que faz a curva no nó i tem height(2*i+1) + height(2*i+2) arestas, uma aresta para cada um desses nós.

Então, experimente cada nó como ponto da curva e mantenha o melhor resultado. No segundo exemplo, o 5 no índice 1 tem altura 2 à esquerda (1, 3) e 2 à direita (9, 4), um caminho de quatro arestas. A raiz tem altura 3 à esquerda e 0 à direita, o que resulta em apenas três.

Cada chamada a height percorre uma subárvore inteira, e um nó é percorrido novamente para cada ancestral acima dele, então o trabalho é O(n·h). Com h ≤ 14, isso é rápido o suficiente aqui, mas em uma árvore de ponteiros em forma de cadeia, h pode chegar a n e a mesma ideia custa O(n²). As chamadas repetidas a height são o desperdício que a última abordagem elimina.

Algoritmo

Escreva height(i): 0 para uma posição vazia; caso contrário, 1 + max(height(2*i+1), height(2*i+2)).
Para cada nó existente i, calcule height(2*i+1) + height(2*i+2).
Retorne a maior dessas somas.

def diameterOfBinaryTree(tree):
    n = len(tree)

    def height(i):
        # Nodes on the longest downward path from i; an empty spot has 0.
        if i >= n or tree[i] == -1:
            return 0
        return 1 + max(height(2 * i + 1), height(2 * i + 2))

    best = 0
    for i in range(n):
        if tree[i] != -1:
            # The longest path that turns at node i goes down both sides.
            best = max(best, height(2 * i + 1) + height(2 * i + 2))
    return best

Uma passagem em pós-ordem pelas alturas

Intuição

A altura de um nó depende apenas das alturas de seus dois filhos, e esses são os mesmos dois números de que a verificação do ponto de virada precisa. Portanto, calcule-os uma vez, de baixo para cima. Uma travessia em pós-ordem termina de processar os dois filhos antes do pai. Em cada nó, você então tem left e right: atualize a resposta com left + right e passe 1 + max(left, right) para o pai.

No primeiro exemplo, a folha 7 retorna 1, o 4 acima dela retorna 2, e o 3 retorna 3, pois seu outro filho 1 tem altura 1. O 6 retorna 1. Na raiz, left + right = 3 + 1 = 4, que é a resposta. O melhor resultado oferecido por qualquer outro nó é 3, com 1 + 2 = 3.

Cada nó é visitado uma vez, então o tempo é O(n), e a recursão tem a mesma profundidade da árvore, O(h), aproximadamente um quadro por nível. A resposta é mantida em uma variável fora da recursão, porque o que uma chamada retorna (uma altura) não é o que você deseja ao final (o comprimento de um caminho).

Algoritmo

Defina best = 0 e escreva height(i). Para um espaço vazio, retorne 0.
Calcule left = height(2*i+1) e right = height(2*i+2).
Defina best como o maior entre best e left + right.
Retorne 1 + max(left, right).
Chame height(0) e retorne best.

def diameterOfBinaryTree(tree):
    n = len(tree)
    best = 0

    def height(i):
        # Returns the height of node i and updates best on the way back up.
        nonlocal best
        if i >= n or tree[i] == -1:
            return 0
        left = height(2 * i + 1)
        right = height(2 * i + 2)
        best = max(best, left + right)  # the longest path that turns at node i
        return 1 + max(left, right)

    height(0)
    return best

Armadilhas e casos extremos

A maioria das respostas erradas conta a coisa errada ou mede no nó errado.

Contar nós em vez de arestas. O caminho 7, 4, 3, 8, 6 tem cinco nós e comprimento 4, e um único nó tem diâmetro 0.
Medir apenas passando pela raiz. No segundo exemplo, o melhor caminho passando pela raiz tem três arestas, e a resposta é quatro, com a volta no índice 1.
Retornar o diâmetro da chamada recursiva. O nó pai precisa das alturas dos filhos para construir caminhos mais longos; o diâmetro deve ficar em uma variável separada.
Misturar duas convenções de altura. Com alturas que contam nós e 0 para uma posição vazia, left + right já é a contagem de arestas. Alturas que contam arestas precisam de -1 para uma posição vazia e left + right + 2. Misturar metade de uma convenção com metade da outra resulta em um erro de uma ou duas unidades.
Ler além do fim. Uma folha perto do fim do array pode ter índices de filhos além da última posição. Trate um índice além do fim como uma posição vazia.
Confundir o deslocamento em Lua e R, onde os arrays começam em 1. Mantenha os índices dos nós baseados em 0 para a aritmética de 2*i+1 e leia tree[i + 1].

Perguntas frequentes4

Qual é a complexidade de tempo do diâmetro de uma árvore binária?

A solução em pós-ordem visita cada nó uma vez, então é executada em tempo O(n) e usa O(h) de espaço extra para a recursão, em que h é a altura. Calcular as alturas separadamente em cada nó custa O(n·h), o que se torna O(n²) em uma árvore em formato de cadeia.

O diâmetro de uma árvore binária sempre passa pela raiz?

Não. O caminho mais longo pode estar inteiramente dentro de uma subárvore, por exemplo, quando a raiz tem um ramo curto e uma subárvore profunda e ramificada do outro lado. É por isso que você verifica left + right em cada nó, não apenas na raiz.

O diâmetro é contado em nós ou em arestas?

Aqui, ele é contado em arestas, os links entre nós consecutivos no caminho, então um único nó tem diâmetro 0 e dois nós conectados têm diâmetro 1. Alguns livros contam os nós em vez disso, o que resulta em um a mais. Confira qual das formas o problema solicita antes de adicionar ou subtrair 1.

Como encontrar o diâmetro de uma árvore binária sem recursão?

Visite os nós em uma ordem na qual cada filho venha antes de seu pai. Uma maneira: coloque a raiz em uma pilha, retire os nós da pilha e adicione-os a uma lista enquanto coloca seus filhos na pilha; depois percorra essa lista de trás para frente. Armazene a altura de cada nó em um array, leia as alturas dos dois filhos em cada nó e atualize a resposta com a soma delas. O tempo continua sendo O(n).

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

tree = [8, 3, 6, 1, 4, -1, -1, -1, -1, 7]

Esperado

Diameter of Binary Tree

Função

Restrições

Exemplos

Dicas

Solução

Meça cada par de nós

Meça ambas as alturas em cada nó

Uma passagem em pós-ordem pelas alturas

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos