Camino más corto de raíz a hoja

Question

¿Cuál es la forma más sencilla, preferiblemente mediante recursividad, de encontrar la ruta más corta de raíz a hoja en un BST (árbol de búsqueda binaria)?Se prefiere Java, el pseudocódigo está bien.

¡Gracias!

Answer 1

Descripción general:

Usar una Búsqueda en amplitud (BFS) en contraposición a un Búsqueda en profundidad (DFS).Encuentre el primer nodo sin hijos.

Al usar un DFS, es posible que tengas suerte en algunos árboles de entrada (pero no hay forma de saber que tuviste suerte, por lo que aún necesitas buscar en todo el árbol), pero usar el método BFS es mucho más rápido y puedes encontrar una solución sin tocar todos. nodos.

Para encontrar la ruta de raíz a hoja, puede seguir el primer nodo sin hijos encontrado hasta la raíz utilizando la referencia principal.Si no tiene ninguna referencia principal almacenada en cada nodo, puede realizar un seguimiento de los nodos principales a medida que avanza hacia abajo.Si tiene su lista en orden inverso, puede colocarla toda en una pila y luego sacarla.

Pseudocódigo:

El problema es muy simple;aquí hay un pseudocódigo para encontrar la longitud más pequeña:

1. Coloque el nodo raíz en la cola.

Repita mientras la cola no esté vacía y no se haya encontrado ningún resultado:

2. Extraiga un nodo del principio de la cola y compruebe si no tiene hijos.Si no tiene hijos, ya ha hecho el camino más corto.
3. De lo contrario, empuje a todos los niños (izquierda, derecha) a la cola.

Encontrar todos los caminos más cortos:

Para encontrar todas las rutas más cortas, puede almacenar la profundidad del nodo junto con el nodo dentro de la cola.Luego continuaría el algoritmo para todos los nodos de la cola con la misma profundidad.

Alternativa:

Si, en cambio, decidiera utilizar un DFS, tendría que buscar en todo el árbol para encontrar el camino más corto.Pero esto podría optimizarse manteniendo un valor para el más corto hasta el momento y solo verificando la profundidad de los nodos futuros hasta encontrar un nuevo más corto, o hasta llegar al más corto hasta el momento.Sin embargo, BFS es una solución mucho mejor.

Answer 2

Esto está en C++, pero es tan simple que puedes convertirlo fácilmente.Simplemente cambie min a max para obtener la profundidad máxima del árbol.

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

Solo para explicar lo que esto hace, cuenta desde el nodo hoja (devuelve 0 cuando encuentra una hoja) y cuenta hacia atrás hasta la raíz.Hacer esto para los lados izquierdo y derecho del árbol y tomar el mínimo le dará el camino más corto.

Answer 3

La primera búsqueda en amplitud es exactamente óptima en términos del número de vértices visitados.¡Tienes que visitar cada uno de los vértices que visitarías en una búsqueda primero en amplitud solo para demostrar que tienes la hoja más cercana!

Sin embargo, si tiene el mandato de utilizar la recursividad, el enfoque de Mike Thompson es casi el correcto de usar y es un poco más simple.

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 (raíz de TreeNode) {

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

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

}