Shortest Path Root a Folha

Question

O que é a maneira mais fácil, de preferência usando recursão, para encontrar o caminho mais curto raiz-folha em um BST (Binary Pesquisa Tree). Java preferido, pseudocódigo bem.

Obrigado!

Answer 1

Descrição geral:

Use a em largura de pesquisa (BFS) em oposição a um busca em profundidade (DFS) . Encontrar o primeiro nó sem filhos.

Usando um DFS você pode ter sorte em algumas árvores de entrada (mas não há nenhuma maneira de saber que você teve sorte assim você ainda precisa pesquisar toda a árvore), mas utilizando o método BFS é muito mais rápido e você pode encontrar uma solução sem tocar em todos os nós.

Para encontrar a raiz para caminho folha, você poderia seguir o primeiro encontrado nó sem filhos todo o caminho de volta até a raiz usando a referência pai. Se você não tem nenhuma referência pai armazenado em cada nó, você pode acompanhar os nós pai como você recurse para baixo. Se você tem sua lista em ordem inversa você poderia empurrar tudo em uma pilha e, em seguida, pop-lo.

Pseudo-código:

O problema é muito simples; aqui é pseudo-código para encontrar o menor comprimento:

1. Coloque o nó raiz na fila.

Repetir enquanto a fila não está vazia, e sem resultado foi encontrado:

2. Puxe um nó a partir do início da fila e verificar se ele não tem filhos. Se ele não tem filhos você são feitos você encontrou o caminho mais curto.
3. Caso contrário empurrar todas as crianças (esquerda, direita) para a fila.

Encontrar todos os caminhos mais curtos:

Para encontrar todos os caminhos mais curtos você pode armazenar a profundidade do nó juntamente com nó dentro da fila. Então você teria que continuar o algoritmo para todos os nós na fila com a mesma profundidade.

Alternativa:

Se em vez você decidiu usar uma DFS, você teria que pesquisar toda a árvore para encontrar o caminho mais curto. Mas isso poderia ser otimizado, mantendo um valor para o menor até agora, e só verificar a profundidade de futuro os nós até encontrar um novo mais curto, ou até atingir o menor até agora. A BFS é uma solução muito melhor embora.

Answer 2

Esta é em C ++, mas é tão simples que você pode convertê-lo facilmente. Basta alterar min no máximo para obter a profundidade máxima árvore.

int TreeDepth(Node* p)
{
    return (p == NULL) ? 0 : min(TreeDepth(p->LeftChild), TreeDepth(p->RightChild)) + 1;
}

Apenas para explicar o que isso está fazendo, ele está contando a partir do nó de folha (ele retorna 0 quando encontra uma folha) e conta-se de volta para a raiz. Fazer isso para os lados da mão esquerda e direita da árvore e tendo o mínimo vai dar-lhe o caminho mais curto.

Answer 3

Amplitude primeira pesquisa é exatamente ideal em termos de número de vértices visitados. Você tem que visitar cada um dos vértices que você visitar em uma amplitude primeira pesquisa apenas, a fim de provar que você tem a folha mais próxima!

No entanto, se você tem um mandato para uso recursão, a abordagem de Mike Thompson é quase o direito de uso -. E é ligeiramente mais simples

TD(p) is
  0 if p is NULL (empty tree special case)
  1 if p is a leaf (p->left == NULL and p->right == NULL)
  min(TD(p->left), TD(p->right)) if p is not a leaf 

Answer 4

static int findCheapestPathSimple (TreeNode raiz) {

if(root==null){
    return 0; 
}

return root.data+Math.min(findCheapestPathSimple(root.left), findCheapestPathSimple(root.right));

}