Кратчайший путь от корня к листу

Question

Какой самый простой способ, предпочтительно с использованием рекурсии, найти кратчайший путь от корня к листу в BST (Binary Search Tree). Java предпочтительнее, псевдокод в порядке.

Спасибо!

Answer 1

Общее описание:

Используйте Поиск в ширину (BFS) в отличие от Поиск в глубину (DFS) . Найти первый узел без детей.

Используя DFS, вам может повезти на некоторых входных деревьях (но нет способа узнать, что вам повезло, поэтому вам все равно нужно искать по всему дереву), но использование метода BFS намного быстрее, и вы можете найти решение не касаясь всех узлов.

Чтобы найти путь от корня к листу, вы можете пройти по первому найденному бездетному узлу до самого корня, используя родительскую ссылку. Если у вас нет родительской ссылки, хранящейся в каждом узле, вы можете отслеживать родительские узлы по мере их восстановления. Если у вас есть список в обратном порядке, вы можете поместить его в стек, а затем вытолкнуть.

Псевдо-код:

Проблема очень проста; Вот псевдокод, чтобы найти наименьшую длину:

1. Поместить корневой узел в очередь.

Повторите, пока очередь не пуста, и ничего не найдено:

2. Вытащите узел из начала очереди и проверьте, нет ли у него дочерних элементов. Если у вас нет детей, вы Готово, вы нашли кратчайший путь.
3. В противном случае все дети (слева, справа) помещаются в очередь.

Поиск всех кратчайших путей:

Чтобы найти все кратчайшие пути, вы можете сохранить глубину узла вместе с узлом внутри очереди. Затем вы продолжите алгоритм для всех узлов в очереди с одинаковой глубиной.

Альтернатива:

Если вместо этого вы решили использовать DFS, вам придется искать по всему дереву, чтобы найти кратчайший путь. Но это можно оптимизировать, сохранив значение для самого короткого до сих пор и проверяя только глубину будущих узлов до тех пор, пока вы не найдете новый самый короткий, или пока вы не достигнете самого короткого до сих пор. BFS - намного лучшее решение.

Answer 2

Это в C ++, но это так просто, что вы можете легко конвертировать его. Просто измените min на max, чтобы получить максимальную глубину дерева.

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

Просто чтобы объяснить, что это делает, он считает от узла листа (он возвращает 0, когда находит лист) и считает обратно до корня. Выполнение этого для левой и правой сторон дерева и получение минимума даст вам кратчайший путь.

Answer 3

static int findCheapestPathSimple (корень TreeNode) {

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

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

}

Answer 4

Поиск в ширину в точности оптимален с точки зрения количества посещенных вершин. Вы должны посетить каждую из вершин, которые вы посетили в первом поиске, только чтобы доказать, что у вас самый близкий лист!

Однако, если у вас есть мандат на использование рекурсии, подход Майка Томпсона будет почти правильным - и немного проще.

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