Описание тега least-common-ancestor
0
ответов
Наименьший общий предок со складкой скалы?
На интервью мне задали вопрос о том, как описать метод нахождения LCA на бинарном дереве. Я с моей идеей. В конце концов, интервьюер сказал, что это можно сделать с помощью функции складки скалы... но я не знаю, как, какие идеи?
06 окт '13 в 13:44
1
ответ
Нахождение наименьшего общего предка в двоичном дереве с помощью o(h^2) для изменения
Прежде чем подумать о написании функции для ее выполнения, я попытаюсь придумать алгоритм. h обозначается как максимальное расстояние между основным родителем и данным узлом. Он должен работать в o(h^2), что означает, что такой алгоритм должен быть …
19 июн '15 в 23:10
2
ответа
Как найти первого общего предка узла в двоичном дереве?
Ниже приведен мой алгоритм поиска первого общего предка. Но я не знаю, как рассчитать сложность времени, кто-нибудь может помочь? public Tree commonAncestor(Tree root, Tree p, Tree q) { if (covers(root.left, p) && covers(root.left, q)) retur…
11 май '11 в 11:54
3
ответа
Определить наименьшего общего предка во время компиляции
Существует множество вопросов по поводу алгоритма наименьшего общего предка, но этот отличается, потому что я пытаюсь определить LCA во время компиляции, и мое дерево не является ни двоичным, ни деревом поиска, даже если моя упрощенная версия может …
11 апр '16 в 14:48
2
ответа
Что не так с этим алгоритмом наименьшего общего предка?
В ходе собеседования мне задали следующий вопрос: При наличии корневого узла (в правильно сформированном двоичном дереве) и двух других узлов (которые гарантированно находятся в дереве и также различаются), возвращают наименьшего общего предка двух …
07 дек '14 в 10:39
1
ответ
Найти наименее общего предка двух узлов в Java
Я посмотрел на множество других ответов на stackru и не могу найти ничего, что работает, я либо получаю root, либо сам вернул node1, я не уверен, как сделать это рекурсивно, и перепробовал много раз, заканчивая так же. Любая помощь будет принята с б…
06 дек '13 в 06:05
2
ответа
Нахождение наименьшего общего предка из таблицы переходного закрытия
У меня есть таблица, представляющая транзитивное замыкание организационной иерархии (то есть, это дерево с одним корнем): create table ancestry ( ancestor integer, descendant integer, distance integer ); У меня есть другая таблица, которая содержит …
31 янв '13 в 00:32
0
ответов
LCA двоичного дерева из двух узлов, если эти два узла встречаются много раз
Это моя реализация моего двоичного дерева (это не код для Lca, просто нормальная реализация двоичного дерева, просто чтобы дать представление о том, как я построил двоичное дерево) void insert(int n) { create(&root,n); } void create(node** temp,…
17 июн '13 в 07:39
1
ответ
Найти наиболее посещаемый узел на графике
В графе N узлов, соединенных ровно N-1 ребрами. Существует ровно 1 кратчайший путь от одного узла к любому другому узлу. Узлы пронумерованы от 1 до N. Даны Q запросов, которые сообщают исходный узел и узлы назначения. Найдите наиболее посещаемый узе…
23 ноя '18 в 16:44
2
ответа
Проблема LCA на собеседовании
Иногда я сталкиваюсь с такими вопросами на собеседовании: "Найти общего родителя любых двух узлов в дереве". Я заметил, что они задают вопросы LCA также в Google, Amazon и т. Д. Как сказано в википедии, LCA можно найти путем пересечения путей от зад…
26 дек '10 в 14:05
6
ответов
Алгоритм самого низкого общего предка
Поэтому я пытался реализовать алгоритм с наименьшим общим предком. Я посмотрел на множество различных алгоритмов (в основном, варианты решения Траяна или варианты RMQ). Я использую недвоичное дерево. Мое дерево будет часто меняться между запросами, …
14 июн '11 в 02:31
2
ответа
Найти несколько LCA в корне дерева
Я пытаюсь реализовать LCA для корня дерева. Я дал дерево (связный неориентированный граф без циклов) и последовательность запросов о LCA для некоторого корня и двух вершин. Каждый конкретный запрос может иметь различный корень, поэтому я не могу исп…
18 авг '14 в 20:54
2
ответа
Дочерние узлы LCA
Я пытаюсь получить наименее общего предка двух узлов в дереве. Я попробовал, но проблема в том, if one node is the descendant node for other Я не смог получить LCA. Я попытался решить его, тогда он работал только для узлов-потомков. Не знал, как пос…
13 мар '13 в 10:43
3
ответа
Есть ли лучший способ найти наименьшего общего предка?
Я знаю, что подобные вопросы задавались ранее, но я думаю, что мое решение намного проще. Особенно по сравнению с Википедией. Пожалуйста, докажите, что я не прав! Если у вас есть дерево с узлами, которые имеют данную структуру данных: struct node { …
30 окт '10 в 02:26
0
ответов
Неясное понимание алгоритма самого низкого общего предка (LCA)
Я пытался выучить алгоритм LCA O(nlog n) и предварительную обработку O(log n). Я читаю его с русского сайта с помощью google translate. Но он плохо переводится, и мне трудно понять его Кто-нибудь может мне помочь с этим? Это псевдокод, который я взя…
14 окт '15 в 15:40
1
ответ
Подход минимального диапазона <O (n), O (1)> (от дерева к ограниченному RMQ)
Итак, я прочитал этот учебник TopCoder по RMQ (Range Minimum Query), и у меня возник большой вопрос. В разделе, где он представил этот подход, я могу понять до сих пор следующее: (В целом подход использует методологию, представленную в алгоритме Spa…
08 фев '13 в 17:08
1
ответ
Поиск наименьшего общего предка в нерекурсивной версии двоичного дерева - Java
Я ищу нерекурсивную версию алгоритма поиска наименее общего предка в отсортированном двоичном дереве, написанном на Java. Все, что я нашел, это только рекурсивная версия (даже на stackru и на других сайтах). Может кто-нибудь написать или направить м…
21 дек '14 в 14:26
2
ответа
Какая временная сложность для LCA в бинарном дереве, реализованном в Java здесь
У меня есть этот код, чтобы найти least common Ancestor из двух nodes в binary tree, Я думаю, что сложность времени O(log n), но мнения экспертов необходимы. Этот код довольно хорошо работает на моих входах, но я не уверен, что я полностью его проте…
29 янв '14 в 06:12
1
ответ
Наиболее эффективный алгоритм проверки того, находится ли лист c в том же поддереве, что и листья a и b
В настоящее время я работаю над программой, одним из шагов которой является проверка того, находится ли лист c в том же поддереве, что и два других листа a и b, в двоичном дереве T. Мой текущий подход заключается в следующем: сначала найдите LCA каж…
17 июн '15 в 19:18
1
ответ
Модификация кода LCA для двоичного дерева, чтобы проверить, присутствует ли узел в Java
У меня есть этот код, который рассчитывает Least common Ancestor из двух nodes в Binary tree, В настоящее время предполагается, что оба узла присутствуют. Я могу написать вспомогательный метод только для проверки наличия узлов, а затем вызвать LCABT…
29 янв '14 в 17:34