Validate Binary Search Tree
Uma árvore binária é armazenada no array tree 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), -1 marca uma posição vazia, e o array pode terminar com entradas -1 extras.
Escreva isValidBST, que retorna true se a árvore for uma árvore de busca binária e false caso contrário. Em uma árvore de busca binária, 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.
Função
- treeinteger-array
- árvore binária em ordem por nível, com -1 para uma posição vazia
- Retornaboolean
- true se a árvore for uma árvore de busca binária, false caso contrário
Restrições
1 ≤ tree.length ≤ 32767- Cada
tree[i]é-1ou um valor com0 ≤ 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ó. - Ambos os filhos de uma posição vazia 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
- Lidos em ordem (subárvore esquerda, nó, subárvore direita), os valores são
1, 3, 6, 8, 10, 12, 15. Eles aumentam estritamente, então cada nó fica no lado correto de cada ancestral.
- 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 o
6no índice5está na subárvore direita da raiz, então deve ser maior que10.
- Entrada
- tree = [12, 7, 12]
- Saída
- false
- Explicação
- O filho à direita da raiz contém
12, igual à raiz. A subárvore à direita deve ser estritamente maior, então a árvore não é válida.
Para ir além
O pai de um nó está no índice (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 usar uma pilha ou recursão?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Em
[10, 5, 15, -1, -1, 6, 20], todo 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 aumenta o limite inferior parav.Mantenha uma pilha de
(index, low, high), começando pela raiz e usando 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 existente com seu intervalo ajustado.
Solução
A regra abrange subárvores inteiras, então comparar cada nó com seus dois filhos não é suficiente: um nó em um nível mais profundo pode violar um limite definido por um ancestral vários níveis acima. Leia a árvore em ordem e verifique se os valores aumentam estritamente, ou passe a cada nó o intervalo permitido por seus ancestrais.
Compare cada nó com suas subárvores inteiras
Intuição
Cada valor à esquerda de um nó é menor que seu valor v exatamente quando o maior valor desse lado é menor que v, e cada valor à direita é maior que v exatamente quando o menor valor desse lado é maior que v. Duas funções auxiliares recursivas os encontram. Um lado vazio retorna -1 ou 100001, fora do intervalo de valores, portanto nunca falha.
Cada nó é percorrido uma vez para cada ancestral, cerca de n × h visitas para uma árvore de profundidade h. Com uma profundidade de no máximo 14, isso é barato, mas em um caminho de n nós, cresce para O(n²).
Algoritmo
- Percorra todos os índices
icujo valor não seja-1. - Encontre o maior valor na subárvore esquerda em
2*i+1(-1se estiver vazia) e o menor na subárvore direita em2*i+2(100001se estiver vazia). - Se o maior valor for maior ou igual a
tree[i], ou o menor for menor ou igual atree[i], retornefalse. - 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 devem aumentar estritamente
Intuição
Uma travessia em ordem visita a subárvore esquerda, depois o nó e, em seguida, a subárvore direita; assim, em uma árvore de busca binária, os valores são lidos em ordem crescente.
O inverso também é válido. Para qualquer nó v, toda a sua subárvore esquerda vem imediatamente antes dele na sequência, e toda a sua subárvore direita vem imediatamente depois. Se a sequência for estritamente crescente, todo valor antes de v é menor, e todo valor depois dele é maior; portanto, a regra vale para v e para todos os nós.
O segundo exemplo resulta em 5, 10, 6, 15, 20: a queda de 10 para 6 revela o nó fora de posição. Cada nó é visitado uma vez: tempo O(n) e espaço O(n) para a lista.
Algoritmo
- Escreva
walk(i): se a posição estiver vazia, pare; caso contrário, percorra2*i+1, acrescentetree[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
Cada ancestral impõe um limite a um nó: abaixo de a se o nó estiver na subárvore esquerda de um ancestral que contém a, acima de a se estiver na subárvore direita. Juntos, os limites formam um intervalo aberto (low, high), e o nó está no lugar certo exatamente quando seu valor está estritamente dentro dele.
Construa o intervalo ao descer. Um filho esquerdo mantém low e recebe high = v; um filho direito mantém high e recebe low = v. No segundo exemplo, 15 passa (10, 15) para seu filho esquerdo, e o 6 falha imediatamente. Os valores estão entre 0 e 10^5, então -1 e 100001 servem como ausência de limite. Cada nó é verificado uma vez, em tempo O(n), com O(h) nós na pilha.
Algoritmo
- Empilhe
(0, -1, 100001): a raiz, sem limite real. - Desempilhe
(i, low, high). Setree[i]não estiver estritamente entrelowehigh, retornefalse. - Empilhe cada filho existente: o da esquerda em
2*i+1com(low, tree[i]), o da direita em2*i+2com(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
- Comparar um nó apenas com seus filhos. Em
[10, 5, 15, -1, -1, 6, 20], cada par de pai e filho parece correto, mas o6viola o limite da raiz. - Permitir valores iguais.
[12, 7, 12]não é válido: compare com<, nunca com≤. - Usar
0como limite inferior para “sem limite”. Isso rejeita a árvore válida[0]. - Ler um filho sem verificar
2*i+1 < tree.length. Em[12, 7, 12], o índice3está além do fim. - Em Lua e R, os arrays começam em 1. Mantenha os índices dos nós baseados em 0 para
2*i+1e leiatree[i + 1].
Perguntas frequentes3
Qual é a complexidade de tempo para validar uma árvore de busca binária?
A verificação em ordem e a verificação de intervalo visitam cada nó uma vez: tempo O(n), com espaço extra O(h) para a pilha da verificação de intervalo em uma árvore de profundidade h. Comparar cada nó com suas subárvores inteiras custa O(n × h), chegando a O(n²) em uma árvore em formato de caminho.
Você consegue validar uma BST com uma travessia em ordem sem armazenar todos os valores?
Sim. A verificação compara cada valor apenas com o anterior, então mantenha o valor anterior em uma variável em vez de uma lista e retorne false assim que um valor não for maior. O espaço extra cai para O(h) por causa da recursão ou da pilha.
Uma árvore binária de busca pode conter valores duplicados?
Não segundo a definição estrita usada aqui: um valor igual não se encaixa em nenhum dos lados. Alguns livros didáticos permitem valores iguais em um dos lados, por exemplo, à direita. Segundo essa regra, uma das comparações estritas passa a ser ≤.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def isValidBST(tree):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumento
tree = [8, 3, 12, 1, 6, 10, 15]
Saída Esperada
true