Наименее распространенный поиск предков в двоичном дереве не рекурсивная версия - Java

Question

Я ищу нерекурсивную версию алгоритма поиска наименее общего предка в сортированном двоичном дереве, написанном на Java. Все, что я нашел, это только рекурсивная версия, здесь, в Stackoverflow и на других сайтах.

Может ли кто-нибудь написать или направить меня к нерекурсивной версии (используя цикл while)? Также пишите, если эта версия более эффективна с точки зрения временной сложности?

Answer 1

Просто случилось видеть этот давно забытый вопрос.

ли вы имеете в виду что-то подобное, если вы получаете дерево:

 A 
    B  C 
D E F G 
H I J K L M N O 

commonAncestor(L,G) = C 
commonAncestor(H,O) = A 
commonAncestor(B,H) = B 

что-то подобное?

2 методов, чтобы дать (все предположить, предоставленные узлы в дереве):

Если есть ссылка на родитель (т.е. вы направляете от B обратно в А), то решение легко, подобно поиску Пересечение связанного списка:

найти глубину узлов Node1 и Node2, если глубина равна D1 и D2. Найдите разницу между D1 и D2 (при условии, что d). Имейте указатель на Node1 и Node2 (предположите p1 и p2). Для узла с большей глубиной перейдите к родительским d-м раз. На данный момент p1 и p2 будут иметь ту же глубину под предком. Просто используйте простой цикл для навигации как p1, так и p2 до родителя, пока не нажмете на узел, который p1 == p2.

---

Если родительское звено в узле, вы можете итеративно перемещаться по дереву:

currentNode = root; 
while (true) { 
    if ((currentNode > node1 && currentNode < node2) || 
     (currentNode < node1 && currentNode > node2)) { 
     break; // current node is the common ancestor, as node1 and node2 
       // will go to different sub-tree 
    } else if (currentNode > node1) { 
     currentNode = currentNode.left; 
    } else { // currentNode < node1/2 
     currentNode = currentNode.right; 
    } 
} 

// currentNode will be the answer you want