二叉树非递归版本中最不常见的祖先搜索 - Java

Question

>我正在搜索一种非递归算法版本，用于在用 Java 编写的排序二叉树中查找最不常见的祖先。我找到的所有内容都只是递归版本(即使在堆栈溢出和其他网站上(。

有人可以写或引导我到非递归版本(使用 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 (，那么解决方案很容易，类似于查找相交的链表：

查找节点 1 和节点 2 的深度，假设深度为 D1 且D2 。 找出D1和D2之间的差异(假设d(。 具有指向节点 1 和节点 2 的指针(假设为 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

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