Каков наилучший способ найти ближайших родителей для двух заданных узлов на дереве?
Так что, если у меня есть:Поиск ближайшего родителя для двух узлов
1
/ \
2 3
/\ /\
4 5 6 7
ближайший родительский для 5 и 6 будет один.
Thanks
Эта проблема называется проблемой наименьшего общего предка (LCA). (Google это)
Один запрос может быть просто восхождение вверх по их parent ссылкам, пока они не встретятся:
Первый шаг, чтобы нижний подъем узла, пока они не находятся в одной и той же height.
Второй шаг - дать им возможность подняться одновременно до тех пор, пока не встретится на том же узле.
Тогда этот узел является LCA этих двух узлов.
Если вам нужно обработать несколько запросов, вам нужно использовать более продвинутый алгоритм. Наиболее эффективный по времени алгоритм использует O (n) время до препроцесса и O (1) время для каждого запроса, где n - это общее количество узлов в дереве.
Какое у вас есть входное представление и древовидное представление? Например, вы задаете корень, каждый узел имеет указатели на дочерние элементы, и вы знаете, какие значения двух узлов нужно искать? Вы указываете вместо этого узлы, и каждый узел имеет указатель на родителя? Может ли быть неполное двоичное дерево без указателей, и вы даете индексы двух узлов? – 6502
Я пробовал: до тех пор, пока наши родители разные, мы являемся родителями и делаем чек снова. – smallB
Ввод - это два узла. – smallB