Symmetric Tree
Você recebe uma árvore binária armazenada no array tree em ordem por nível. A raiz fica no índice 0, os filhos do nó no índice i ficam em 2*i+1 (à esquerda) e 2*i+2 (à direita), -1 marca uma posição vazia, e o array pode terminar com entradas extras -1. Retorne true se a árvore for uma imagem espelhada de si mesma em torno de uma linha vertical que passa pela raiz e false caso contrário. Tanto a estrutura quanto os valores devem corresponder.
Função
- treeinteger-array
- a árvore binária em ordem por nível, com -1 para uma posição vazia
- Retornaboolean
- true se a árvore é um espelho de si mesma, false caso contrário
Restrições
1 ≤ tree.length ≤ 32767- Cada
tree[i]é-1ou um valor com0 ≤ tree[i] ≤ 1000. tree[0]nunca é-1, então a árvore tem pelo menos um nó.- A matriz pode terminar com entradas
-1extras 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 = [1, 2, 2, 3, 4, 4, 3]
- Saída
- true
- Explicação
- Dobre a árvore ao meio. Os dois
2nos índices1e2se encontram, os3externos nos índices3e6se encontram, e os4internos em4e5se encontram.
- Entrada
- tree = [1, 2, 2, -1, 3, -1, 3]
- Saída
- false
- Explicação
- Ambos os
3ficam pendurados à direita de seus pais. Em uma imagem espelhada, o filho direito do2à esquerda (índice4) deve ficar de frente para o filho esquerdo do2à direita (índice5), e o índice5está vazio.
- Entrada
- tree = [4, 6, 6, 5, -1, -1, 9]
- Saída
- false
- Explicação
- A forma é uma imagem espelhada: o índice
3fica de frente para o índice6, e ambos contêm um nó. Seus valores são diferentes:5contra9; portanto, a árvore não é simétrica.
+16 testes ocultos ao enviar
Para ir além
Se a forma é espelhada, mas alguns valores não são, qual é o menor número de valores de nós que você precisa alterar para tornar a árvore simétrica?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Com qual nó o filho esquerdo da raiz precisa corresponder? E com qual nó o filho esquerdo desse nó precisa corresponder?
Compare duas posições por vez. Elas são espelhadas quando ambas estão vazias ou quando ambas contêm o mesmo valor e os filhos se cruzam: o filho esquerdo de uma espelha o filho direito da outra, e o filho direito de uma espelha o filho esquerdo da outra.
Mantenha uma pilha de pares de índices, começando com
(1, 2). Remova um par da pilha: ignore-o se as duas posições estiverem vazias, falhe se apenas uma estiver vazia ou se os valores forem diferentes; caso contrário, adicione(2*a+1, 2*b+2)e(2*a+2, 2*b+1)à pilha.
Solução
Simetria é uma propriedade de pares. Todo nó tem um parceiro na posição espelhada do outro lado da raiz, e o parceiro de um filho esquerdo é um filho direito. Portanto, você nunca compara um nó com seus próprios filhos: percorre as duas metades da árvore em direções opostas ao mesmo tempo, compara a estrutura e o valor de cada par e para no primeiro par que não corresponde.
Compare cada nível com seu inverso
Intuição
Primeiro, como percorrer o array. O nó no índice i tem o filho esquerdo no índice 2*i+1 e o filho direito no índice 2*i+2. Um filho é real apenas se seu índice estiver dentro do array e o valor nesse índice não for -1. Em [1, 2, 2, 3, 4, 4, 3], a raiz 1 tem filhos nos índices 1 e 2, e o 2 no índice 1 tem filhos nos índices 3 e 4.
Agora observe a árvore um nível de cada vez. Uma imagem espelhada é igual da esquerda para a direita e da direita para a esquerda, então cada nível, incluindo os espaços vazios, deve ser igual nos dois sentidos. No primeiro exemplo, os níveis abaixo da raiz são 2 2 e 3 4 4 3. No segundo, eles são 2 2 e depois -1 3 -1 3; invertida, essa sequência fica 3 -1 3 -1, então a resposta é false.
Os espaços vazios precisam permanecer na sequência. Sem eles, o nível inferior do segundo exemplo seria 3 3 e passaria. Escreva uma entrada para cada posição de filho de cada nó real no nível, usando -1 para uma posição vazia; os filhos de posições vazias também são vazios, então não acrescentam nada. Cada nó é visitado uma vez, então o tempo é O(n), e apenas um nível é mantido na memória de cada vez: O(w) para o nível mais largo w.
Algoritmo
- Comece com uma lista que contenha o índice da raiz
0. - Para cada índice da lista, da esquerda para a direita, anote as posições dos dois filhos: o valor do filho, se ele existir, ou
-1se estiver vazio. Reúna os filhos existentes para o próximo nível. - Se essa linha de posições dos filhos for diferente de sua inversa, retorne
false. - Passe para o próximo nível e repita até que ele esteja vazio; então, retorne
true.
def isSymmetric(tree):
n = len(tree)
level = [0] # the real nodes of one level, left to right
while level:
row = [] # the child spots under this level, -1 for an empty one
next_level = []
for i in level:
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
row.append(tree[child])
next_level.append(child)
else:
row.append(-1)
if row != row[::-1]:
return False
level = next_level
return TrueRecursão em pares espelhados
Intuição
Em vez de níveis inteiros, compare duas subárvores: a subárvore esquerda da raiz, que começa no índice 1, e a subárvore direita, que começa no índice 2. Dois pontos são espelhados quando ambos estão vazios ou quando ambos contêm o mesmo valor e seus filhos se cruzam. O filho esquerdo de um espelha o filho direito do outro (o par externo), e o filho direito de um espelha o filho esquerdo do outro (o par interno).
No primeiro exemplo, mirrors(1, 2) compara os dois 2s e, em seguida, chama mirrors(3, 6) para os 3s externos e mirrors(4, 5) para os 4s internos. Cada uma dessas chamadas encontra apenas pontos vazios abaixo e retorna true. No segundo exemplo, mirrors(4, 5) encontra um 3 no índice 4 diante de um ponto vazio no índice 5, retorna false, e o false sobe de volta até o topo.
Cada nó real pertence a, no máximo, um par, então o tempo é O(n). A pilha de chamadas tem a mesma profundidade da árvore, O(h), que aqui é de, no máximo, 14 quadros.
Algoritmo
- Escreva
mirrors(a, b). Uma posição está vazia quando seu índice ultrapassa o fim ou contém-1. Se as duas posições estiverem vazias, retornetrue; se apenas uma estiver, retornefalse. - Se
tree[a]etree[b]forem diferentes, retornefalse. - Caso contrário, retorne
mirrors(2*a+1, 2*b+2)emirrors(2*a+2, 2*b+1). - Retorne
mirrors(1, 2). Uma raiz sem filhos resulta em duas posições vazias, o que étrue.
def isSymmetric(tree):
n = len(tree)
def mirrors(a, b):
# Spots a and b must hold the same value, or both be empty.
empty_a = a >= n or tree[a] == -1
empty_b = b >= n or tree[b] == -1
if empty_a or empty_b:
return empty_a and empty_b
return (tree[a] == tree[b]
and mirrors(2 * a + 1, 2 * b + 2) # outer pair
and mirrors(2 * a + 2, 2 * b + 1)) # inner pair
return mirrors(1, 2)Pilha explícita de pares espelhados
Intuição
A recursão precisa de apenas uma coisa: os pares que ainda estão esperando para ser verificados. Mantenha esses pares em uma pilha própria e as chamadas desaparecem. Comece com o par (1, 2). Remova um par da pilha. Se as duas posições estiverem vazias, não há nada abaixo delas, então prossiga. Se uma estiver vazia ou os valores forem diferentes, a árvore não é simétrica. Caso contrário, adicione à pilha o par externo (2*a+1, 2*b+2) e o par interno (2*a+2, 2*b+1).
A ordem em que você verifica os pares não importa, porque a árvore só é simétrica se todos os pares corresponderem. Uma pilha segue uma ordem de busca em profundidade; uma fila seguiria a ordem por nível e funcionaria da mesma forma. O terceiro exemplo para no primeiro par inválido, (3, 6), que contém 5 e 9.
Cada remoção da pilha trata um par, e cada nó real aparece em no máximo um par, então o tempo é O(n). A pilha mantém aproximadamente um par pendente por nível do caminho atual, usando espaço O(h), e não há limite de recursão com que se preocupar.
Algoritmo
- Coloque o par
(1, 2)em uma pilha. - Remova um par
(a, b)da pilha. Se as duas posições estiverem vazias (índice além do fim ou-1), passe para o próximo par. - Se apenas uma posição estiver vazia, ou se
tree[a]for diferente detree[b], retornefalse. - Coloque
(2*a+1, 2*b+2)e(2*a+2, 2*b+1)na pilha. - Quando a pilha estiver vazia, retorne
true.
def isSymmetric(tree):
n = len(tree)
stack = [(1, 2)] # pairs of spots that must mirror each other
while stack:
a, b = stack.pop()
empty_a = a >= n or tree[a] == -1
empty_b = b >= n or tree[b] == -1
if empty_a and empty_b:
continue
if empty_a or empty_b or tree[a] != tree[b]:
return False
stack.append((2 * a + 1, 2 * b + 2)) # outer pair
stack.append((2 * a + 2, 2 * b + 1)) # inner pair
return True
Armadilhas e casos extremos
A maioria das respostas erradas compara o par errado de nós ou esquece que um espaço vazio faz parte da forma.
- Verificar cada subárvore por conta própria. A subárvore esquerda não precisa ser simétrica por si só: em
[1, 2, 2, 3, 4, 4, 3], a subárvore2, 3, 4não é, mas a árvore inteira é. Ela precisa espelhar a subárvore direita. - Combinar os filhos do jeito errado. O filho esquerdo de um lado fica em frente ao filho direito do outro:
(2*a+1, 2*b+2)e(2*a+2, 2*b+1), nunca(2*a+1, 2*b+1). - Comparar apenas os valores. Remova os espaços vazios de
[1, 2, 2, -1, 3, -1, 3]e cada nível será lido da mesma forma nos dois sentidos, mas a árvore não será simétrica. Mantenha-1em uma linha de nível ou verifique se os espaços estão vazios no teste dos pares. - Ler além do fim. Um índice além do fim do array corresponde a um espaço vazio. Verifique
a < nantes de lertree[a]; uma árvore com um único nó não tem nenhum índice1ou2. - Parar no primeiro par correspondente. Um par correto não prova nada; retorne
truesomente depois de verificar todos os pares. - Confundir o deslocamento em Lua e R, onde os arrays começam em 1. Mantenha os índices dos nós baseados em 0 para o cálculo
2*i+1e leiatree[i + 1].
Perguntas frequentes4
Qual é a complexidade de tempo de Symmetric Tree?
Cada nó real é comparado uma vez, como parte de um par espelhado, então o tempo é O(n). As versões recursiva e com pilha usam espaço extra O(h) para os pares pendentes ao longo do caminho atual. A versão nível por nível mantém um nível na memória, O(w) para o nível mais largo.
Como verificar se uma árvore binária é simétrica sem recursão?
Mantenha uma pilha ou uma fila de pares de nós que devem espelhar um ao outro, começando pelos dois filhos da raiz. Remova um par, retorne falso se houver uma divergência e adicione o par externo e o par interno dos filhos deles. Se a pilha ficar vazia sem nenhuma divergência, a árvore é simétrica.
Qual é a diferença entre uma árvore simétrica e duas árvores idênticas?
Duas árvores são idênticas quando você compara a esquerda com a esquerda e a direita com a direita. Uma árvore é simétrica quando sua subárvore esquerda é idêntica à imagem espelhada de sua subárvore direita, então a comparação se cruza: esquerda com direita e direita com esquerda. O mesmo código de comparação de pares resolve os dois problemas, com os pares de filhos trocados.
Uma árvore com um único nó é simétrica?
Sim. Um único nó tem dois espaços vazios para filhos, e dois espaços vazios espelham um ao outro. Uma raiz com exatamente um filho nunca é simétrica, porque esse filho fica diante de um espaço vazio.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def isSymmetric(tree):
# Escreva o código aquiCaso 1
Caso 2
Caso 3
Entrada
tree = [1, 2, 2, 3, 4, 4, 3]
Esperado
true