二叉树非递归版本中最少的共同祖先搜索 – Java
我正在搜索一个非递归算法版本，在用Java编写的排序二进制树中查找最不常见的祖先。 我发现的一切只是递归版本（即使在stackoverflow和其他网站上）。
有人可以写或指导我到非递归版本（使用while循环）？ 还要写一下这个版本在时间复杂度方面是否更有效？
碰巧看到这个长期被遗忘的问题。
如果给你一棵树，你的意思是什么？
A BC DEFG HIJKLMNO commonAncestor(L,G) = C commonAncestor(H,O) = A commonAncestor(B,H) = B 这样的事情？
2个给出的方法（所有假设提供的节点都在树中）：
如果有父级的链接（即你从B指向A），那么解决方案很简单，类似于查找交叉链表：
假设深度为D1和D2 ，找到Node1和Node2的深度。 找出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
基本思想是，如果它是二叉搜索树，如果两个节点都比当前节点更大/更小，它将转到相同的子树。 因此，共同的祖先是两个值传递给不同子节点的节点，即当一个小于当前节点而另一个小于当前节点时。