标签: least-common-ancestor

这里的二叉树可能不一定是二进制搜索树.
结构可以视为 -

struct node {
    int data;
    struct node *left;
    struct node *right;
};

我可以和朋友一起解决的最大解决方案就是这种 -
考虑这个二叉树:

二叉树http://lcm.csa.iisc.ernet.in/dsa/img151.gif

顺序遍历产量 - 8,4,9,2,5,1,6,3,7

后序遍历产量 - 8,9,4,5,2,6,7,3,1

因此,例如,如果我们想要找到节点8和5的共同祖先,那么我们在顺序树遍历中创建8到5之间的所有节点的列表,在这种情况下恰好是[4,9] ,2].然后我们检查此列表中的哪个节点在后序遍历中最后出现,即2.因此,8和5的共同祖先是2.

这个算法的复杂性,我相信是O(n)(O(n)对于顺序/后序遍历,其余的步骤再次是O(n),因为它们只不过是数组中的简单迭代).但这很有可能是错误的.:-)

但这是一个非常粗略的方法,我不确定它是否会因某些情况而崩溃.这个问题还有其他(可能是更优的)解决方案吗？

关于最不常见的祖先算法有很多问题,但是这个问题是不同的,因为我试图在编译时确定LCA,而我的树既不是二进制也不是搜索树,即使我的简化版本可能看起来像一.

假设你有一堆包含成员typedef的结构parent,这是另一个类似的结构:

struct G
{
    typedef G parent;    // 'root' node has itself as parent
};

struct F
{
    typedef G parent;
};

struct E
{
    typedef G parent;
};

struct D
{
    typedef F parent;
};

struct C
{
     typedef F parent;
};

struct B
{
    typedef E parent;
};

struct A
{
     typedef E parent;
};

它们共同组成了一棵树

A    B    C    D
 \  /      \  /
  E         F
   \       /
    \ …

所以我一直在研究实现最低共同的祖先算法.我查看了许多不同的算法(主要是Trajan解决方案的变体或RMQ的变体).

我使用的是非二叉树.我的树通常会在查询之间进行更改,因此预处理不一定是值得的.树不应超过50-75个节点.我想知道的是我是否应该使用他们的算法或只是坚持自己的算法.

我的算法

myLCA(node1, node2) {
    parentNode := [ ]
    while (node1!=NULL) {
         parentNode.push(node1)
         node1 := node1.parent
    }
     while (node2!=NULL) {
         for i in parentNode.size {
             if (parentNode(i) == node2) {
                 return node2; 
             }
         }
         node2 := node2.parent
     }

}       

所以,我在RMQ(范围最小查询)上阅读了这个 TopCoder教程,我有一个很大的问题.

在他介绍这种方法的部分,到目前为止我能理解的是:

(整个方法实际上使用稀疏表(ST)算法中引入的方法,从LCA到RMQ的减少,以及从RMQ到LCA)

给定数组A [N],我们需要将其转换为笛卡尔树,从而使RMQ问题成为LCA(最低共同祖先)问题.稍后,我们可以获得阵列A的简化版本,并使其成为受限制的RMQ问题.

所以它基本上是两个转换.所以第一个RMQ到LCA的部分很简单.通过使用堆栈,我们可以在O(n)时间内进行变换,得到一个数组T [N],其中T [i]是元素i的父元素.树完成了.

但这是我无法理解的.O(n)方法需要一个数组|A[i] - A[i-1]| = 1,并且该数组在本教程的从LCA到RMQ的部分中引入.这涉及到这棵树的欧拉之旅.但是,如何通过转换的最终结果实现这一目标？我对它的处理方法不是线性的,所以在这种方法中应该被认为是不好的,对此采用线性方法是什么？

更新:让我困惑的一点

Here's the array A[]:

  n : 0  1  2  3  4  5  6  7  8  9
A[n]: 2  4  3  1  6  7  8  9  1  7

Here's the array T[]:

  n : 0  1  2  3  4  5  6  7  8  9
T[n]: 3  2  0  *  8  4  5  6 …

以下是我找到第一个共同祖先的算法.但我不知道如何计算它的时间复杂度,任何人都可以帮忙吗？

public Tree commonAncestor(Tree root, Tree p, Tree q) {
    if (covers(root.left, p) && covers(root.left, q))
        return commonAncestor(root.left, p, q);
    if (covers(root.right, p) && covers(root.right, q))
        return commonAncestor(root.right, p, q);
    return root;
}
private boolean covers(Tree root, Tree p) { /* is p a child of root? */
    if (root == null) return false;
    if (root == p) return true;
    return covers(root.left, p) || covers(root.right, p);
}

非二叉树通常如何表示？对节点可以拥有的子节点数没有限制的树.是否最好使用邻接矩阵或邻接列表,并假设没有循环,或做类似于这个问题 - >

如何实现非二叉树

当你有一个n-ary树(它们是正确的名字？)时,如果找到该树中两个给定节点/数据值的最小公共祖先,有什么好办法？我能找到的只是处理二叉树的算法,比如这个 - >

static Node lca(Node root,int v1,int v2)
{
  if (root == null || root.data == v1 || root.data == v2) {
    return root;
  }

  Node left = lca(root.left, v1, v2);
  Node right = lca(root.right, v1, v2);

  if (left != null && right != null) {
    return root;
  }

  return (left != null) ? left : right;
}

我一直在浏览"git merge-base",手册页,我无法理解多个合并库是如何发展的.具体来说,我挂在手册页中的下图中:

When the history involves criss-cross merges, there can be more than one best common
ancestor for two commits. For example, with this topology:
  ---1---o---A
      \ /
       X
      / \
  ---2---o---o---B
both 1 and 2 are merge-bases of A and B. Neither one is better than the other (both
are best merge bases). When the --all option is not given, it is unspecified which
best one is output.

我无法理解如何创造这种情况.我试图使用测试存储库在分支之间重新创建这种纵横交错的合并情况,但我无法复制它.在所有情况下,我总是最终得到A和B指向的1个合并提交(而不是A和B指向独立的合并提交,如图所示).

谁能说明这种情况会怎样？这是常见情况还是错误情况？

我正在看这个问题,然后阅读有关Tarjan最不常见的祖先算法.我之前从未遇到任何LCA算法的应用.

常用的LCA算法在哪里？

给定下面的类和接口,我想知道为什么隐式转换:

ISomeModelAbstract<IBasicModel> x = new ConcreteClass();

是不可能的.我试过了

public interface ISomeModelAbstract<out T> where T: IBasicModel

但后来我无法使用GetById和GetAll方法.我感谢任何帮助或提示.谢谢.

public interface IBasicModel {
    string _id { get; set; }
}

public class SomeModel: IBasicModel {
    public string _id { get; set; }

    /* some other properties! */
}

public interface ISomeModelAbstract<T> where T: IBasicModel
{
    bool Save(T model);
    T GetById(string id);
    IEnumerable<T> GetAll();
    bool Update(string id, T model);
    bool Delete(string id);
}

public abstract class SomeModelAbstract<T> : ISomeModelAbstract<T> where T …

我正在尝试为无根树实施LCA.我已经给出了一个树(一个没有循环的连通无向图)和一些关于某些根和两个顶点的LCA的查询.每个特定的查询都可以有不同的根,所以我不能使用在开始时对任意根进行预处理的算法.

到目前为止,我已经尝试使用DFS找到从顶点到根的路径,然后检查它在哪里发散,但是它有点慢(O(nq),其中q是查询数).

有任何建议如何预处理树,以便具有查询的次线性复杂性？

我之前已经问过类似的问题,但我认为我的解决方案要简单得多.特别是与维基百科相比.

请证明我错了!

如果您的树具有具有给定数据结构的节点:

struct node
{
    node * left;
    node * right;
    node * parent;
    int key;
}

你可以写一个这样的函数:

node* LCA(node* m, node* n)
{
    // determine which of the nodes is the leftmost
    node* left = null;
    node* right = null;
    if (m->key < n->key)
    {
        left = m;
        right = n;
    }
    else
    {
        left = n;
        right = m;
    }
    // start at the leftmost of the two nodes,
    // keep moving up the tree …

有时候我遇到的面试问题就像这样:"查找在树中的任何2个节点的公共父".我注意到他们也在谷歌,亚马逊等地提出了LCA问题.

正如维基百科所说, LCA可以通过从给定节点到根的路径的交集来找到,它需要O(H),其中H是树的高度.此外,还有更先进的算法可以在O(N)中处理树,并在O(1)中回答LCA查询.

我想知道访问者究竟想要了解候选人提出这个LCA问题的原因.路径交集的第一个算法似乎微不足道.他们是否希望候选人记住预处理算法？他们是否希望候选人能够即时发明这些算法和数据结构？

这个问题可能已经被很多人提出过,但是,它有点不同.我们有一棵二叉树.而且你有两个节点p&q.我们必须找到最不常见的父母.但是你没有指向根的根节点指针.您将获得两个内置功能:

1)BOOL same(node *p, node *q);- >如果节点相同则返回true,否则返回false.

2)node* parentNode(node *c);- >返回一个节点,该节点是当前节点的父节点.

如果节点c实际上是root,那么parentNode函数将返回一个NULL值.使用我们必须的函数来查找树的最不常见的父代.