Validate Binary Search Tree
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 (à esquerda) e 2*i+2 (à direita), -1 marca uma posição vazia, e o array pode terminar com entradas extras -1.
Escreva uma função chamada isValidBST que retorne true se a árvore for uma árvore binária de busca e false caso contrário. Em uma árvore binária de busca, o valor de cada nó é estritamente maior que todos os valores de sua subárvore esquerda e estritamente menor que todos os valores de sua subárvore direita. Dois valores iguais nunca podem estar ambos em uma árvore válida.
Função
- treeinteger-array
- a árvore binária em ordem por nível, com -1 para uma posição vazia
- Retornaboolean
- verdadeiro se a árvore for uma árvore binária de busca, falso caso contrário
Restrições
1 ≤ tree.length ≤ 32767- Cada
tree[i]é-1ou um valor tal que0 ≤ tree[i] ≤ 105. 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ó. - Os dois filhos de um espaço vazio também estão vazios, e a profundidade é de no máximo
14. - Os valores podem se repetir.
Exemplos
- Entrada
- tree = [8, 3, 12, 1, 6, 10, 15]
- Saída
- true
- Explicação
- Cada nó fica no lado correto de todos os nós acima dele. Lendo em ordem (subárvore esquerda, nó, subárvore direita), os valores aparecem como
1, 3, 6, 8, 10, 12, 15, em ordem estritamente crescente, como ocorre em uma árvore de busca.
- Entrada
- tree = [10, 5, 15, -1, -1, 6, 20]
- Saída
- false
- Explicação
- Cada nó é maior que seu filho esquerdo e menor que seu filho direito, mas a árvore não é válida. O
6no índice5está na subárvore direita da raiz10, então ele precisa ser maior que10, mas não é.
- Entrada
- tree = [12, 7, 12]
- Saída
- false
- Explicação
- O filho direito da raiz contém
12, o mesmo valor que a raiz. A subárvore direita deve ser estritamente maior, então um valor igual viola a regra.
+16 testes ocultos ao enviar
Para ir além
O pai do nó no índice i fica em (i-1)/2, arredondado para baixo. Você consegue percorrer a árvore em ordem usando espaço extra O(1), passando pelos pais em vez de manter uma pilha ou recorrer à recursão?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Em
[10, 5, 15, -1, -1, 6, 20], cada nó é maior que seu filho esquerdo e menor que seu filho direito. Por que ainda assim não é uma árvore de busca?Cada ancestral impõe um limite a um nó: abaixo dele, se o nó estiver à sua esquerda; acima dele, se estiver à sua direita. Juntos, esses limites formam um intervalo aberto. Ir para a esquerda a partir de um valor
vreduz o limite superior parav; ir para a direita eleva o limite inferior parav.Mantenha uma pilha de
(index, low, high), começando pela raiz e com um intervalo mais amplo do que todos os valores permitidos. Remova uma entrada da pilha, falhe se o valor não estiver estritamente dentro do intervalo e adicione cada filho real à pilha com seu intervalo ajustado.
Solução
A regra se aplica a subárvores inteiras, não a um nó e seus dois filhos. Uma árvore pode passar no teste de pai e filho em cada nó e ainda assim estar errada, porque um nó em uma posição mais profunda pode violar um limite definido por um ancestral vários níveis acima. Duas ideias resolvem isso de forma simples: percorrer a árvore em ordem e verificar se os valores aumentam estritamente, ou passar a cada nó o intervalo de valores permitido por seus ancestrais e compará-lo com esse intervalo.
Compare cada nó com suas subárvores inteiras
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 só existe se seu índice estiver dentro do array e o valor nesse índice não for -1. Em [10, 5, 15, -1, -1, 6, 20], a raiz 10 tem 5 e 15 nos índices 1 e 2, e o 15 tem 6 e 20 nos índices 5 e 6.
A primeira ideia que a maioria das pessoas tenta é comparar cada nó apenas com seus dois filhos. Essa árvore explica por que isso falha: 5 < 10, 15 > 10, 6 < 15 e 20 > 15 são verdadeiros, mas o 6 está à direita do 10. A definição fala sobre todos os valores em uma subárvore, então verifique exatamente isso.
Para um nó que contém v, tudo à sua esquerda é menor que v exatamente quando o maior valor à esquerda é menor que v. Da mesma forma, tudo à sua direita é maior que v quando o menor valor ali é maior que v. Dois pequenos auxiliares recursivos encontram esse maior e esse menor valor. Para um lado vazio, o maior valor é -1 e o menor é 100001, valores fora do intervalo permitido, então um lado vazio nunca causa falha.
Isso está correto, mas repete trabalho. Um nó é percorrido uma vez para cada ancestral acima dele, então o total é de cerca de n × h visitas para uma árvore de profundidade h. Com uma profundidade de no máximo 14, isso funciona bem aqui, mas, em uma árvore que seja um único caminho longo de n nós, o total cresce para O(n²).
Algoritmo
- Percorra cada índice
icujo valor não seja-1. - Encontre o maior valor na subárvore esquerda que começa em
2*i+1, ou-1se essa posição estiver vazia. - Encontre o menor valor na subárvore direita que começa em
2*i+2, ou100001se essa posição estiver vazia. - Se o maior valor for maior ou igual a
tree[i], ou o menor valor for menor ou igual atree[i], retornefalse. - Após o último nó, retorne
true.
def isValidBST(tree):
n = len(tree)
def largest(i):
# Largest value in the subtree at index i, or -1 when that spot is empty.
if i >= n or tree[i] == -1:
return -1
return max(tree[i], largest(2 * i + 1), largest(2 * i + 2))
def smallest(i):
# Smallest value in the subtree at index i, or 100001 when that spot is empty.
if i >= n or tree[i] == -1:
return 100001
return min(tree[i], smallest(2 * i + 1), smallest(2 * i + 2))
for i in range(n):
if tree[i] == -1:
continue
# Everything on the left must be smaller, everything on the right larger.
if largest(2 * i + 1) >= tree[i] or smallest(2 * i + 2) <= tree[i]:
return False
return TrueOs valores em ordem simétrica devem aumentar estritamente
Intuição
Uma travessia em ordem visita a subárvore esquerda, depois o nó e, em seguida, a subárvore direita. Em uma árvore binária de busca, essa ordem é ordenada: tudo à esquerda é menor, então vem primeiro, e tudo à direita é maior, então vem depois. O primeiro exemplo resulta em 1, 3, 6, 8, 10, 12, 15.
O inverso também é válido, e é isso que torna essa uma verificação. Pegue qualquer nó v. Na sequência em ordem, toda a subárvore esquerda fica imediatamente antes dele, e toda a subárvore direita, imediatamente depois. Se a sequência for estritamente crescente, todo valor antes de v é menor e todo valor depois dele é maior, então a regra vale para v e, da mesma forma, para todos os outros nós.
Então percorra a árvore em ordem, colete os valores e compare cada um com o anterior. O segundo exemplo resulta em 5, 10, 6, 15, 20: o passo de 10 para 6 revela o nó no lado errado. O terceiro resulta em 7, 12, 12, e o 12 repetido não passa na verificação estrita. Cada nó é visitado uma vez, em tempo O(n), e a lista ocupa espaço O(n).
Algoritmo
- Escreva
walk(i): se a posição estiver vazia, pare; caso contrário, percorra2*i+1, adicionetree[i]e, em seguida, percorra2*i+2. - Chame
walk(0)para coletar os valores em ordem. - Para cada posição
ka partir de1, sevalues[k-1] ≥ values[k], retornefalse. - Retorne
true.
def isValidBST(tree):
n = len(tree)
values = []
def walk(i):
# Left subtree, then the node, then the right subtree.
if i >= n or tree[i] == -1:
return
walk(2 * i + 1)
values.append(tree[i])
walk(2 * i + 2)
walk(0)
# A search tree read in order gives strictly increasing values.
for k in range(1, len(values)):
if values[k - 1] >= values[k]:
return False
return TruePropague o intervalo permitido pela árvore
Intuição
Observe a regra do ponto de vista de um nó. Cada ancestral impõe um limite a ele. Se o nó estiver na subárvore esquerda de um ancestral que contém a, seu valor deve ser menor que a; se estiver na subárvore direita, deve ser maior que a. Todos esses limites juntos formam um intervalo aberto (low, high), e o nó está no lugar certo exatamente quando seu valor está estritamente dentro desse intervalo.
Você pode construir esse intervalo ao descer. A raiz não tem limite. Ao ir de um nó que contém v para o filho esquerdo, mantenha low e reduza high para v; ao ir para o filho direito, mantenha high e aumente low para v. O novo limite é sempre mais restrito do que aquele que substitui, porque o próprio v passou na verificação em relação ao intervalo anterior.
No segundo exemplo, 15 recebe o intervalo (10, no limit) e o repassa ao filho esquerdo como (10, 15). O 6 é menor que 10, então a verificação falha ali mesmo, sem consultar nenhum outro nó. Os valores estão entre 0 e 10^5, então -1 e 100001 servem como “sem limite”.
Mantenha os nós pendentes em uma pilha, cada um com seu intervalo. Cada nó é verificado uma vez, em tempo O(n), e a pilha armazena os nós pendentes ao longo de um caminho, usando espaço O(h). O primeiro intervalo inválido encerra a busca.
Algoritmo
- Empilhe
(0, -1, 100001): o índice da raiz e um intervalo aberto sem limite real. - Retire
(i, low, high)da pilha. Setree[i]não estiver estritamente entrelowehigh, retornefalse. - Se o filho esquerdo
2*i+1for real, empilhe-o com o intervalo(low, tree[i]). - Se o filho direito
2*i+2for real, empilhe-o com o intervalo(tree[i], high). - Quando a pilha estiver vazia, retorne
true.
def isValidBST(tree):
n = len(tree)
# Each entry: a node index and the open range (low, high) its value must fall in.
# -1 and 100001 lie outside every allowed value, so they mean "no limit".
stack = [(0, -1, 100001)]
while stack:
i, low, high = stack.pop()
value = tree[i]
if not (low < value < high):
return False
left, right = 2 * i + 1, 2 * i + 2
if left < n and tree[left] != -1:
stack.append((left, low, value)) # the left side must stay below value
if right < n and tree[right] != -1:
stack.append((right, value, high)) # the right side must stay above value
return True
Armadilhas e casos extremos
A maioria das respostas erradas verifica muito pouco ou verifica a coisa certa usando a comparação errada.
- Comparar um nó apenas com seus filhos. Em
[10, 5, 15, -1, -1, 6, 20], cada par de pai e filho parece correto, mas o6ainda viola o limite definido pela raiz dois níveis acima. - Permitir valores iguais. A ordem é estrita nos dois lados, então
[12, 7, 12]não é válido. Uselow < v < highevalues[k-1] < values[k], nunca≤. - Passar apenas o valor do pai adiante. Um filho à esquerda precisa dos dois limites: abaixo do pai e acima de qualquer limite inferior que o pai tinha. Mantenha o intervalo completo.
- Escolher um valor de “sem limite” que um nó possa conter. Os valores começam em
0, então um limite inferior de0rejeitaria um nó válido que contém0, como em[0]. Comece abaixo de todos os valores permitidos. - Ler além do fim do array. Verifique
2*i+1 < tree.lengthantes de ler um filho e trate-1como ausência de filho. - 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
Por que verificar cada nó em relação aos seus filhos não é suficiente para validar uma BST?
A regra abrange subárvores inteiras. Um nó no fundo da subárvore direita da raiz deve ser maior que a raiz, mesmo que seja filho esquerdo de um nó muito maior. Em [10, 5, 15, -1, -1, 6, 20], o 6 é um bom filho esquerdo de 15, mas fica à direita de 10, então a árvore não é uma árvore de busca. Você precisa dos limites de cada ancestral, não apenas do pai.
Qual é a complexidade de tempo para validar uma árvore de busca binária?
Ambos os métodos padrão, a verificação em ordem e a verificação de intervalo, percorrem cada nó uma vez, então levam O(n) de tempo. A verificação de intervalo precisa de O(h) de espaço extra para a pilha, em que h é a profundidade. Comparar cada nó com todas as suas subárvores também funciona, mas custa O(n × h), que chega a O(n²) em uma árvore em formato de caminho.
Você consegue validar uma BST com uma travessia em ordem sem armazenar cada valor?
Sim. A verificação em ordem compara cada valor apenas com o valor imediatamente anterior, então mantenha o valor anterior em uma variável, em vez de em uma lista. Percorra a árvore em ordem usando recursão ou uma pilha explícita e retorne false assim que um valor não for maior que o anterior. Isso reduz o espaço extra para O(h).
Uma árvore binária de busca pode conter valores duplicados?
Não segundo a definição estrita usada aqui: todo valor à esquerda deve ser menor e todo valor à direita, maior, então dois valores iguais nunca podem se encaixar. Alguns livros didáticos permitem duplicatas de um lado, por exemplo, valores iguais à direita. Segundo essa regra, você alteraria uma das comparações estritas para ≤; portanto, leia a definição antes de escrever a verificação.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def isValidBST(tree):
# Escreva o código aquiCaso 1
Caso 2
Caso 3
Entrada
tree = [8, 3, 12, 1, 6, 10, 15]
Esperado
true