Как определить, лежит ли узел w на пути между узлом u и узлом v в дереве?
Я пытаюсь решить проблему, которая требует от меня определить, лежит ли узел w на пути между узлом u и узлом v в дереве (не обязательно двоичном).
Например, для следующего дерева:
1
2 3
4 5 6 7
Узел 2 лежит на пути от узла 4 до 7.
Очевидным решением было бы получить обход euler по дереву и пройти узлы, которые были посещены между первыми вхождениями обоих узлов. Однако это будет решение O(n) в худшем случае, где n - это количество узлов в дереве. Я где-то читал, что это можно сделать с помощью LCA (Lowest Common Ancestor). Тем не менее, я не могу понять, как. Может ли кто-нибудь, пожалуйста, посоветовать мне?
1 ответ
Скажите A = LCA(u,v). Путь между u и v - это путь от u к A и от A к v. Проверьте каждый из этих узлов (поднимаясь от u, а затем вверх от v). Если w среди них, то он на пути, в противном случае это не так.