Самый низкий общий предок для данной пары узлов

Question

Я наткнулся на этот вопрос. Ниже мой подход:

Lets say the two nodes are node1 and node2 
For any node (lets say node1), find the path from Root to 
     node1 and store it in an HashMap 
For the other node node2, find the path from root to node2, and while traversing back, 
     check if any of the nodes are present in the hashmap or not 
Return the first found node 

Время Сложность O (п) и Space Сложность также O (h), где п высота дерева

Я просто хотел бы знать, насколько хорошо этот подход. Или существует ли другое лучшее решение.

EDIT: Данное дерево представляет собой двоичное дерево, а не BST. Таким образом, время поиска узла линейно зависит от размера узлов.

Answer 1

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

Я думаю, this article объясняет вещи очень хорошо. Отправьте ответ, если у вас есть какие-либо вопросы.

Answer 2

Как представлено дерево? В частности, есть ли ссылка на родительский узел любого узла дерева? Это упорядоченное дерево?

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

Я думаю, что найти путь от корня до узла (как ваш подход имеет его) О (п), где п размера дерева, если дерево не заказано ...

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

Answer 3

Настоящая инструкция по решению проблемы Lowest Common Ancestor.

[Range Минимальный запрос и наименьший общий предок] [1]

[1]: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Lowest общий предок (LCA)