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），那么解决方案很简单，类似于查找相交链表：

假设深度为D1和，求 Node1 和 Node2 的深度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

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