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

Вопрос не будет полным, если мы не упомянем об альтернативных методах для обхода объектов.

В настоящее время многие известные библиотеки JavaScript предоставляют свои собственные методы для итерации над коллекциями, то есть над массивов , объектов и в виде массива . Эти методы удобны в использовании и полностью совместимы с любым браузером.

  1. Если вы работаете с jQuery, вы можете использовать метод jQuery.each() . Его можно использовать для беспрепятственной итерации по обоим объектам и массивам:
    $.each(obj, function(key, value) {
        console.log(key, value);
    });
    
  2. В Underscore.js вы можете найти метод _.each() , который выполняет итерацию по списку элементов, каждый из которых, в свою очередь, передается в заданную функцию (обратите внимание на порядок аргументов в функции iteratee !):
    _.each(obj, function(value, key) {
        console.log(key, value);
    });
    
  3. Lo-Dash предоставляет несколько методов для итерации поверх свойств объекта , Основной _.forEach() (или его псевдоним _.each()) полезен для циклического перемещения по обоим объектам и массивам, однако (!) Объекты с свойством length рассматриваются как массивы, и чтобы избежать такого поведения, предлагается использовать методы _.forIn() и _.forOwn() (они также имеют первый аргумент value):
    _.forIn(obj, function(value, key) {
        console.log(key, value);
    });
    
    _.forIn() выполняет итерацию по и унаследовал перечислимые свойства объекта, тогда как _.forOwn() выполняет итерацию только над собственными свойствами объекта (в основном проверяя функцию hasOwnProperty). Для простых объектов и литералов объектов любой из этих методов будет работать нормально.

Как правило, все описанные методы имеют одинаковое поведение с любыми поставленными объектами. Кроме того, использование нативного цикла for..in обычно будет быстрее , чем любая абстракция, например jQuery.each(), эти методы значительно проще в использовании, требуют меньше кодирования и обеспечивают лучшую обработку ошибок.

12
задан Josh Mein 14 September 2012 в 18:37
поделиться

3 ответа

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

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

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

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

Псевдокод:

Проблема очень проста; вот псевдо код для нахождения наименьшей длины:

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

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

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

Нахождение всех кратчайших путей:

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

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

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

15
ответ дан 2 December 2019 в 19:56
поделиться

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

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

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

2
ответ дан 2 December 2019 в 19:56
поделиться

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

Однако, если у Вас есть мандат использовать рекурсию, подход Mike Thompson является почти правильным для использования - и немного более прост.

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 
0
ответ дан 2 December 2019 в 19:56
поделиться
Другие вопросы по тегам:

Похожие вопросы: