二叉树非递归版本中最少的共同祖先搜索 - Java [英] Least common ancestor search in binary tree non recursive version - Java

问题描述

我正在搜索一个非递归算法版本，用于在用Java编写的已排序二进制树中查找最不常见的祖先。
我找到的所有内容都只是递归版本（即使是在stackoverflow和其他网站上）。

I am searching a non recursive algorithm version of finding the least common ancestor in a sorted binary tree written in Java. Everything I found is only the recursive version (even on stackoverflow and on other websites).

有人可以写或指导我到非递归版本（使用while循环）？
如果这个版本在时间复杂度方面效率更高，还可以写一下吗？

Can some one write or direct me to the non recursive version (using while loop)? Also write if this version is more efficient in terms of time complexity?

推荐答案

碰巧看到这个早已被遗忘问题。

Just happened to see this long forgotten question.

如果给你一棵树，你的意思是：

Do you mean something like, if you are given a tree:

       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个方法（所有假设所提供的节点都在树中）：

2 methods to give (all assume the provided nodes are in the tree):

如果有父节点的链接（即你指向从B回到A），然后解决方案很简单，类似于查找交叉链表：

If there are link to parent (i.e. you are pointing from B back to A), then solution is easy, similar to finding intersecting linked list:

查找Node1和Node2的深度，假设深度为 D1 和 D2 。找出 D1 和 D2 之间的区别（假设 d ） 。有指向Node1和Node2的指针（假设p1和p2）。对于具有更高深度的节点，导航到父d次。此时， p1 和 p2 将在祖先下方具有相同的深度。只需一个简单的循环就可以将 p1 和 p2 导航到父级，直到你点击<$ c $的节点c> p1 == p2 。

find depth of Node1 and Node2, assuming the depth is D1 and D2. Find the difference between D1 and D2 (assuming d). Have pointer to Node1 and Node2 (assume p1 and p2). For the node with higher depth, navigate to parent d-th times. At this point, p1 and p2 will have same depth beneath the ancestor. Just have a simple loop to navigate both p1 and p2 to parent, until you hit the node that p1 == p2.

如果节点中没有父链接，则可以迭代地导航树：

If no parent link in node, you can iteratively navigate the tree:

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

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

The basic idea is, given it is a binary search tree, if two nodes are both larger / smaller than current node, it will goes to same child tree. So the common ancestor is the node that two values goes to different children, i.e. when one is smaller than current node and the other one is larger.

这篇关于二叉树非递归版本中最少的共同祖先搜索 - Java的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！