Поиск наименьшего общего предка в нерекурсивной версии двоичного дерева - Java

Question

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

Может кто-нибудь написать или направить меня к нерекурсивной версии (используя цикл 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 обратно на A), то решение легко, аналогично нахождению пересекающегося связанного списка:

найти глубину 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

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