java - 二叉树非递归版本中的最不常见祖先搜索 - 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 指向 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, or we actually 
                // found node1/2 and the other node is its child
    } else if (currentNode > node1) {
        currentNode = currentNode.left;
    } else { // currentNode < node1/2
        currentNode = currentNode.right;
    }
}

// currentNode will be the answer you want

基本思想是，假设它是一个二叉搜索树，如果两个节点都大于/小于当前节点，它将转到同一子树。因此，共同祖先是两个值传递给不同子节点的节点，即当一个小于当前节点而另一个大于当前节点时。