наименьший общий предок (LCM), связанных с корневым узлом

Question

Предполагая, что у меня есть ниже бинарное дерево поиска,

 30 
     /\ 
    /\ 
    8 52 
    /\ 
/\ 
    3 20 
     /\ 
    /\ 
    10 29 

Что такое LCM следующее:

• 30 и 8
• 20 и 29

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

Answer 1

Это довольно легко, так как это дерево поиска, но по вашему запросу я не буду предоставлять слишком много деталей.

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

2) Иначе, учитывая, что это дерево поиска, вы можете быстро определить, какие поддеревы они появятся. Подумайте, что вы должны делать (a), если они находятся в левом поддереве, (b) если они находятся в правом поддереве, или (c) один находится слева, а один справа.

Удачи вам!

Answer 2

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

Таким образом, здесь 30 представляет собой LCM 30 и 8. И 20 - это LCM 20 и 29. LCM 20 и 52 составляет 30, поскольку это самый низкий узел, который имеет как 20, так и 52 в качестве потомков.

Answer 3

Самый низкий общий предок может быть определен в качестве единственного узла в дереве, которое удовлетворяет двум условиям:

A. все целевые узлы являются либо этот узел или decendent этого узла и Б. нет дети этого узла удовлетворяют условию A

Итак, вы ищете узел, где условие A истинно для узла, но ни один из его дочерних элементов. Мы знаем, что корневой узел удовлетворяет условию A (по определению). Таким образом, алгоритм выглядит следующим образом, начиная с корнем:

1. , если этот узел находится в целевом списке, то она является LCA
2. иначе искать ребенок для узлов, удовлетворяющих условию А,
3. для любого удовлетворения, начала снова на шаге 1 для этого ребенка
4. , если никто не удовлетворяет, то у вас есть наименьший общий предок

Этот алгоритм будет работать для любого числа целей, а не только 2, как и в вашем вопросе.

Я знаю, что вам не нужен код, но я рекомендую вам взглянуть на использование потоков Java 8 для этого: они довольно элегантны для такого типа ситуаций, в которых вы выполняете итерацию через детей, ища условия, которые должны быть выполнены.