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

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 (n), а Сложность пространства - также O (h), где n - высота деревазнаю, насколько хорош этот подход.Или существует ли какое-либо другое лучшее решение.

РЕДАКТИРОВАТЬ: данное дерево Binary Tree, а не BST.Таким образом, время, затрачиваемое на поиск узла, зависит от размера узлов.

Answer 1

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

Я думаю эта статья объясняет все очень хорошо. Напишите, если у вас есть какие-либо вопросы, пожалуйста.

Answer 2

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

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

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

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

Answer 3

Вот инструкция по решению проблемы самого низкого общего предка.

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

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