在二叉树非递归版本中最少见的祖先搜索 - 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指向），那么解决方案是容易的，类似于寻找相交链表：

查找节点1和节点2的深度，假设深度为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