Есть два дерева. Каждый узел дерева содержит некоторое значение, которое мы можем сравнивать со значением из другого узла другого дерева. Если значения равны - значит узлы равны.
Каждый узел может содержать от 0 до произвольного количества детей.
Нужно определить, можно ли в этих двух деревьях построить одинаковые пути? То есть такие пути, значения из узлов вдоль которых совпадают. Оба пути должны проходить от вершины до узла содержащего 0 детей. Количество узлов вдоль путей конечно тоже должно быть равным.
Пример:
a a a
/|\ /|\ / \
b c d 1 d z x y
| | |\ | | |
e f g h x g s
У первых двух деревьев есть общий путь "adg". У третьего дерева нет общих путей с первыми двумя деревьями.
Существует ли какой-то общепринятый готовый алгоритм для решения такой задачи? Если существует, то как он может называться и где про него можно почитать?