Kth Smallest Element in a BST
Você recebe uma árvore binária de busca como o array root 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), e -1 indica uma posição vazia. O array pode terminar com entradas extras -1. Em cada nó, a subárvore à esquerda contém apenas valores menores, e a subárvore à direita, apenas valores maiores.
Retorne o k-ésimo menor valor da árvore, contando a partir de 1.
Função
- rootinteger-array
- a árvore de busca binária em ordem por nível, com -1 para um espaço vazio
- kinteger
- a posição a ser encontrada em ordem crescente, começando em 1
- Retornainteger
- o k-ésimo menor valor na árvore
Restrições
1 ≤ root.length ≤ 32767- Cada
root[i]é-1ou um valor com0 ≤ root[i] ≤ 105. root[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. - A regra de ordenação vale em todos os nós, portanto nenhum valor aparece duas vezes.
1 ≤ k ≤o número de nós na árvore.
Exemplos
- Entrada
- root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22]k = 4
- Saída
- 29
- Explicação
- Em ordem crescente, os valores são
6, 17, 22, 29, 41, 65, 90, e o quarto é29. Ele é o maior dos quatro valores na subárvore à esquerda da raiz.
- Entrada
- root = [12, 5, -1, 2, 9, -1, -1, -1, -1, 7, -1, -1, -1, -1, -1]k = 1
- Saída
- 2
- Explicação
- O menor valor encerra o caminho que continua indo para a esquerda:
12,5,2. O7abaixo de9e o preenchimento com-1não mudam isso.
Para ir além
Se a árvore muda com frequência e você precisa encontrar muitas vezes o k-ésimo menor valor, o que cada nó poderia armazenar para que cada consulta leve O(h)?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Qual forma de percorrer uma árvore de busca binária lista seus valores do menor para o maior?
Percorrer a subárvore esquerda, depois o nó e, em seguida, a subárvore direita produz a ordem ordenada. O k-ésimo valor que esse percurso produz é a resposta, então você pode parar ali.
Use uma pilha. A partir do nó atual, empilhe os nós enquanto avança para o filho à esquerda. Remova o elemento do topo e conte-o; pare na
k-ésima remoção. Caso contrário, avance para o filho à direita do nó removido em2*i+2e repita.
Solução
Uma travessia em ordem (subárvore esquerda, nó, subárvore direita) lê os valores de uma árvore de busca binária em ordem crescente, então o k-ésimo valor que ela alcança é a resposta. Faça a travessia usando sua própria pilha e pare nesse ponto; não é necessário ordenar.
Coletar todos os valores e ordenar
Intuição
Ignore a forma: mantenha cada elemento que não seja -1, ordene e retorne a posição k-1. No primeiro exemplo, a lista ordenada é 6, 17, 22, 29, 41, 65, 90, e a posição 3 contém 29.
Isso está correto para qualquer árvore, ordenada ou não. Esse também é o seu custo: ignora a ordem que a árvore já tem e paga O(n log n) pela ordenação e O(n) de memória para a cópia.
Algoritmo
- Reúna cada entrada de
rootque não seja-1. - Ordene os valores reunidos em ordem crescente.
- Retorne o valor na posição
k-1.
def kthSmallest(root, k):
values = [v for v in root if v != -1] # every node, in any order
values.sort()
return values[k - 1]Travessia em ordem para uma lista
Intuição
Abaixo de qualquer nó, a subárvore esquerda contém apenas valores menores, e a subárvore direita, apenas valores maiores. Percorra a subárvore esquerda, depois o nó e, em seguida, a subárvore direita, e faça o mesmo dentro de cada subárvore: cada nó fica depois de todos os valores menores e antes de todos os valores maiores, então a saída fica ordenada. No primeiro exemplo, a travessia produz 6, 17, 22, 29, 41, 65, 90.
Uma passagem substitui a ordenação: tempo O(n) e espaço O(n) para a lista. Ainda assim, ela percorre a árvore inteira, mesmo para k = 1, quando a resposta está no fim do caminho mais à esquerda.
Algoritmo
- Escreva
inorder(i): retorne em uma posição vazia (após o fim ou-1). - Caso contrário, chame
inorder(2*i+1), acrescenteroot[i]à lista e, em seguida, chameinorder(2*i+2). - Chame
inorder(0). - Retorne a entrada da lista na posição
k-1.
def kthSmallest(root, k):
n = len(root)
values = []
def inorder(i):
if i >= n or root[i] == -1:
return
inorder(2 * i + 1) # smaller values first
values.append(root[i])
inorder(2 * i + 2) # then larger ones
inorder(0)
return values[k - 1] # values is sortedEm ordem iterativa que para em k
Intuição
Uma pilha explícita permite interromper a travessia no meio. Vá para a esquerda o máximo que puder, empilhando cada nó. O nó no topo é o menor valor ainda não contado, porque tudo o que é menor está na subárvore esquerda, que está vazia ou já foi contado. Desempilhe e conte-o; sua subárvore direita vem em seguida na ordem crescente.
Para k = 4 no primeiro exemplo: empilhe 41, 17, 6. Desempilhe 6, depois 17 e vá para o filho direito dele: empilhe 29 e 22. Desempilhe 22 e, depois, 29, o quarto. A travessia nunca toca em 65 nem em 90.
A pilha contém no máximo um nó por nível, então o espaço é O(h). A travessia desce uma vez e depois desempilha k vezes: tempo O(h + k).
Algoritmo
- Comece com uma pilha vazia e
i = 0. - Enquanto
ifor um nó real, empilhe-o e vá para2*i+1. - Desempilhe o elemento do topo para
ie subtraia1dek. - Se
kagora for0, retorneroot[i]. - Caso contrário, vá para
2*i+2e volte à etapa 2.
def kthSmallest(root, k):
n = len(root)
stack = [] # nodes whose left side is being visited, deepest on top
i = 0
while True:
while i < n and root[i] != -1: # go as far left as you can
stack.append(i)
i = 2 * i + 1
i = stack.pop() # the smallest value not counted yet
k -= 1
if k == 0:
return root[i]
i = 2 * i + 2 # then everything in its right subtree
Armadilhas e casos extremos
- Ler o array na ordem dos índices. A ordem por nível não é ordenada: o primeiro exemplo começa com
41, 17, 65. - Erro de uma unidade em
k. A contagem começa em1: retorne a posiçãok-1da lista e pare a travessia quando a contagem chegar ak. - Pular a subárvore direita após desempilhar. No segundo exemplo,
9e7ficam na subárvore direita de5, e a travessia nunca os contaria. - Tratar um filho ausente como real. Um filho está vazio quando seu índice ultrapassa o fim ou contém
-1:22está no índice9, então seus filhos19e20estão além do fim. - Os arrays em Lua e R começam em 1. Mantenha os índices dos nós baseados em 0 para
2*i+1e leiaroot[i + 1].
Perguntas frequentes3
Qual é a complexidade de tempo para encontrar o k-ésimo menor elemento em uma BST?
A caminhada iterativa em ordem leva O(h + k) de tempo e O(h) de espaço extra para uma árvore de profundidade h. No pior caso, k = n ou uma árvore em forma de caminho, isso é O(n).
Como encontrar o k-ésimo maior elemento em uma BST?
Espelhe o percurso: subárvore direita, depois o nó e, em seguida, a subárvore esquerda. Isso lista os valores em ordem decrescente. Vá o mais à direita possível enquanto empilha, desempilhe e conte, e vá para o filho esquerdo após cada desempilhamento. O k-ésimo desempilhamento é o k-ésimo maior valor.
Como interromper uma travessia recursiva em ordem no k-ésimo valor?
Mantenha um contador fora da recursão, começando em k. Subtraia 1 depois que a subárvore esquerda de um nó retornar e registre o valor do nó quando o contador chegar a 0. Após cada chamada, retorne imediatamente se a resposta tiver sido registrada. Assim, a recursão corresponde à versão com pilha: tempo O(h + k), espaço O(h).
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def kthSmallest(root, k):
# Escreva o código aquiTeste #1
Teste #2
Argumentos
root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22] k = 4
Saída Esperada
29