Самый короткий путь от корня до листьев

Ответ 1

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

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

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

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

Псевдо-код:

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

• Поместите корень node в очередь.

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

2. Потяните a node с начала очереди и проверьте, нет ли у него детей. Если у вас нет детей, что вы нашли кратчайший путь.
3. В противном случае нажмите все дочерние элементы (слева, справа) в очередь.

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

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

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

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

Ответ 2

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

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

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

Ответ 3

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

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

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 

Ответ 4

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

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

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

}