Range Sum of BST
Você recebe uma árvore binária de busca armazenada no array tree em ordem por nível, e dois números low e high. 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. Em uma árvore binária de busca, todo valor na subárvore esquerda de um nó é menor que o valor do nó, e todo valor na subárvore direita é maior.
Escreva uma função chamada rangeSumBST que retorne a soma de todos os valores dos nós v tais que low ≤ v ≤ high, ou 0 quando nenhum valor estiver nesse intervalo.
Função
- treeinteger-array
- a árvore binária de busca em ordem por nível, com -1 para uma posição vazia
- lowinteger
- o menor valor a contar
- highinteger
- o maior valor a ser contado
- Retornainteger
- a soma dos valores dos nós entre low e high, incluindo ambos
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ó.- O array 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. - A árvore é uma árvore binária de busca válida, então todos os seus valores são distintos.
0 ≤ low ≤ high ≤ 105- A resposta cabe em um inteiro com sinal de 32 bits.
Exemplos
- Entrada
- tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]low = 9high = 31
- Saída
- 88
- Explicação
- Os valores de
9a31são10,12,15,20e31, que somam88.3,8e40estão fora do intervalo.
- Entrada
- tree = [50, 25, 75, -1, -1, -1, -1]low = 60high = 70
- Saída
- 0
- Explicação
- A árvore contém
25,50e75, e nenhum deles está entre60e70, então a soma é0. As quatro entradas-1são os espaços vazios dos filhos de25e75.
- Entrada
- tree = [6, 2, 9, 1, 4, 7]low = 4high = 4
- Saída
- 4
- Explicação
- Com
lowehighambos iguais a4, apenas um nó com valor4é contabilizado. O4no índice4é o filho direito de2, então a resposta é4.
+14 testes ocultos ao enviar
Para ir além
Se você tivesse que responder a milhares de consultas diferentes (low, high) na mesma árvore, como poderia responder a cada uma em tempo O(log n)?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Visitar cada nó e somar os valores no intervalo fornece a resposta correta. O que a ordem da árvore de busca revela sobre os valores abaixo de um nó?
Tudo na subárvore esquerda de um nó é menor que o nó, e tudo na subárvore direita é maior. Se o valor do nó for menor ou igual a
low, algo à esquerda dele pode estar dentro do intervalo?Percorra a árvore com uma pilha de índices a partir da raiz. Adicione o valor de um nó quando ele estiver no intervalo, empilhe seu filho esquerdo no índice
2*i+1somente quando o valor for maior quelowe seu filho direito no índice2*i+2somente quando o valor for menor quehigh.
Solução
Somar todos os valores do intervalo é uma travessia simples: visite cada nó e mantenha aqueles que se encaixam. A ordenação da árvore de busca permite fazer melhor. O valor de um nó indica em que lado estão os valores menores e maiores, então subárvores inteiras podem ser ignoradas sem olhar para nenhum nó dentro delas.
Visite cada nó
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 é válido somente se seu índice estiver dentro do array e o valor nessa posição não for -1. Em [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15], a raiz 20 tem 8 e 31 nos índices 1 e 2, o 12 no índice 4 tem 10 e 15 nos índices 9 e 10, e o 31 tem um espaço vazio à esquerda no índice 5.
Agora, a ideia. Todo valor no intervalo está em algum nó, então uma travessia que alcança todos os nós e soma os valores que satisfazem low ≤ v ≤ high obtém a soma correta. Use uma pilha de índices de nós. Comece pela raiz, retire um índice da pilha, some seu valor se ele estiver no intervalo e empilhe cada filho válido.
Isso ignora completamente a propriedade da árvore de busca; funciona em qualquer árvore binária. Percorre todos os n nós, com tempo O(n), e a pilha armazena os filhos pendentes ao longo de um caminho, usando espaço O(h) para profundidade h. Quando o intervalo abrange poucos valores em uma árvore com milhares de nós, a maior parte desse trabalho é desperdiçada.
Algoritmo
- Coloque o índice da raiz
0em uma pilha e definatotal = 0. - Retire um índice
ida pilha. Selow ≤ tree[i] ≤ high, adicionetree[i]atotal. - Coloque
2*i+1e2*i+2na pilha quando estiverem dentro do array e não forem-1. - Quando a pilha estiver vazia, retorne
total.
def rangeSumBST(tree, low, high):
n = len(tree)
total = 0
stack = [0] # node indexes still to visit; the root is never empty
while stack:
i = stack.pop()
value = tree[i]
if low <= value <= high:
total += value
left, right = 2 * i + 1, 2 * i + 2
if left < n and tree[left] != -1:
stack.append(left)
if right < n and tree[right] != -1:
stack.append(right)
return totalPode com a ordem da árvore de busca
Intuição
Mantenha a mesma travessia com pilha, mas use a ordem. Digamos que um nó contenha v. Sua subárvore esquerda contém apenas valores menores que v. Se v ≤ low, todos eles são menores que low, então a subárvore esquerda não pode acrescentar nada: ignore-a. Da mesma forma, se v ≥ high, a subárvore direita contém apenas valores maiores que high: ignore-a. Portanto, você empilha o filho esquerdo somente quando v > low, e o filho direito somente quando v < high.
No primeiro exemplo, com o intervalo [9, 31], 31 é igual a high, então seu filho direito 40 nunca é empilhado. 8 é menor que low, então seu filho esquerdo 3 é ignorado, enquanto seu filho direito 12 ainda é visitado, porque valores entre 8 e 20 podem estar no intervalo.
Os nós visitados são os k valores no intervalo, mais no máximo dois caminhos da raiz até uma folha ao longo de suas bordas; portanto, o tempo é O(h + k). Quando o intervalo cobre a árvore inteira, isso ainda é O(n), mas um intervalo estreito em uma árvore grande toca apenas algumas dezenas de nós. A pilha precisa de O(h) de espaço.
Algoritmo
- Coloque o índice da raiz
0em uma pilha e definatotal = 0. - Retire um índice
ida pilha e leiav = tree[i]. Selow ≤ v ≤ high, adicionevatotal. - Se
v > low, coloque o filho esquerdo2*i+1na pilha quando ele for real. - Se
v < high, coloque o filho direito2*i+2na pilha quando ele for real. - Quando a pilha estiver vazia, retorne
total.
def rangeSumBST(tree, low, high):
n = len(tree)
total = 0
stack = [0] # node indexes still to visit; the root is never empty
while stack:
i = stack.pop()
value = tree[i]
if low <= value <= high:
total += value
left, right = 2 * i + 1, 2 * i + 2
# Smaller values sit on the left, larger on the right: skip a side the range cannot reach.
if value > low and left < n and tree[left] != -1:
stack.append(left)
if value < high and right < n and tree[right] != -1:
stack.append(right)
return total
Armadilhas e casos extremos
A maioria das respostas incorretas decorre dos limites do intervalo ou do array.
- Usar comparações estritas. As duas extremidades estão incluídas, então um nó igual a
lowouhighconta. - Podar uma etapa cedo demais. Quando
vé igual alow, a subárvore esquerda pode ser ignorada, mas quandovélow + 1, não pode: ela pode conter o própriolow. - Parar em um nó fora do intervalo. Um nó abaixo de
lowainda pode ter uma subárvore direita cheia de valores dentro do intervalo, então ignore apenas o lado descartado pelas regras de ordenação. - Ler o índice de um filho além do fim do array. Verifique
2*i+1 < tree.lengthantes de ler o valor 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
Qual é a complexidade de tempo de Range Sum of BST?
Uma travessia que poda usando a ordem da árvore de busca visita os k nós no intervalo, além dos nós em no máximo dois caminhos a partir da raiz, em tempo O(h + k) para uma árvore de profundidade h. No pior caso, quando todos os valores estão no intervalo, isso é O(n). O espaço extra é O(h) para a pilha ou a recursão.
Por que você pode pular subárvores em Range Sum of BST?
Em uma árvore de busca binária, todo valor à esquerda de um nó é menor do que ele, e todo valor à direita é maior. Se o valor do nó for menor ou igual a low, nada à esquerda dele pode estar dentro do intervalo; e, se for maior ou igual a high, nada à direita pode estar. Ignorar esses lados nunca faz com que um valor dentro do intervalo seja perdido.
O problema da soma em um intervalo de uma BST pode ser resolvido com uma travessia em ordem?
Sim. Uma travessia em ordem de uma árvore de busca binária lista os valores em ordem crescente, então você pode somar os valores quando eles atingirem low e parar assim que um ultrapassar high. Ela fornece a mesma resposta, e a parada antecipada economiza trabalho no lado direito da árvore, enquanto a busca com poda também economiza trabalho no lado esquerdo.
Você deve usar recursão ou uma pilha para Range Sum of BST?
Ambas funcionam. A recursão é mais curta e, aqui, a profundidade é de no máximo 14, então a pilha de chamadas permanece pequena. Uma pilha explícita evita completamente o limite de recursão, o que é importante em uma árvore alta com milhares de níveis, e é o que as soluções desta página usam.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def rangeSumBST(tree, low, high):
# Escreva o código aquiCaso 1
Caso 2
Caso 3
Entrada
tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15] low = 9 high = 31
Esperado
88