algorithm - 如何找到一棵树的最低共同祖先？

Question

有没有办法不使用额外空间来查找 nary tree 的 LCA。我使用一个字符串来保存两个节点的预排序并找到公共前缀

Answer 1

如果节点“知道”它们的深度——或者你愿意让空间来计算节点的深度，你可以从较低的节点备份到较高节点的相同深度，然后再上一层直到他们见面的时间。

取决于在这种情况下“额外空间”的含义。你可以用一个整数来做到这一点——两个节点的深度差。是不是空间太大了？

另一种可能性是您没有父指针，您可以使用指针反转 - 每次遍历指针时，记住您来自的位置，记住您将下一次遍历的指针，然后在下一次指针遍历之前, 将该指针替换为后退指针。上树时必须扭转这一点才能恢复它。这将一个指针的空间作为临时空间。另一个整数可以在您上下工作时保持深度。对您寻找的两个节点同步执行此操作，以便您可以从较低的节点向上工作，直到您在两次遍历中处于相同高度，然后从两个节点向上工作直到您位于公共节点. 这需要三个额外的内存 - 每个当前深度一个，一个用于指针反转期间使用的临时。非常节省空间。这值得么？

Answer 2

返回并为二叉树做这件事。如果您可以为二叉树执行此操作，则可以为 n 叉树执行此操作。

这是二叉树中 LCA 的链接：

以下是将其转换为 n 叉树 LCA 后的样子：

  public class LCA {

    public static <V> Node<V> 
                lowestCommonAncestor(Node<V> argRoot, Node<V> a, Node<V> b) {

      if (argRoot == null) {
        return null;
      }

      if (argRoot.equals(a) || argRoot.equals(b)) {
        // if at least one matched, no need to continue
        // this is the LCA for this root
        return argRoot;
      }

      Iterator<Node<V>> it = argRoot.childIterator();
      // nr of branches that a or b are on, 
      // could be max 2 (considering unique nodes)
      int i = 0; 
      Node<V> lastFoundLCA = null;
      while (it.hasNext()) {
        Node<V> node = lowestCommonAncestor(it.next(), a, b);
        if (node != null) {
          lastFoundLCA = node;
          i++ ;
        }
        if (i >= 2) {
          return argRoot;
        }
      }

      return lastFoundLCA;
    }

  }

Answer 3

对两个节点进行同步遍历。

• 从 LCA=root 开始；
• 环形：
• 找到 A 的步骤和 B 的步骤
• 如果这些相等 { LCA= 步骤；下降A；下降 B; 转到循环；}
• 完成：LCA 现在包含 A 和 B 的 LCA

C中的伪代码：

struct node {
        struct node *offspring[1234];
        int payload;
        };

        /* compare function returning the slot in which this should be found/placed */
int find_index (struct node *par, struct node *this);

struct node *lca(struct node *root, struct node *one, struct node *two)
{
struct node *lca;
int idx1,idx2;

for (lca=root; lca; lca=lca->offspring[idx1] ) {
    idx1 = find_index(lca, one);
    idx2 = find_index(lca, two);
    if (idx1 != idx2 || idx1 < 0) break;
    if (lca->offspring[idx1] == NULL) break;
    }
return lca;
}