如何在任何二叉树中找到两个节点的最低共同祖先？

Question

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

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),因为它们只不过是数组中的简单迭代).但这很有可能是错误的.:-)

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

Answer 1

root如果您发现任何节点具有p或者q作为其直接子节点,则从节点开始并向下移动,那么它就是LCA.(编辑 - 这应该是if p或者q是节点的值,返回它.否则当其中一个p或者q是另一个的直接子节点时它会失败.)

否则,如果您p在其右侧(或左侧)子树q及其左侧(或右侧)子树中找到一个节点,那么它就是LCA.

固定代码如下:

treeNodePtr findLCA(treeNodePtr root, treeNodePtr p, treeNodePtr q) {

        // no root no LCA.
        if(!root) {
                return NULL;
        }

        // if either p or q is the root then root is LCA.
        if(root==p || root==q) {
                return root;
        } else {
                // get LCA of p and q in left subtree.
                treeNodePtr l=findLCA(root->left , p , q);

                // get LCA of p and q in right subtree.
                treeNodePtr r=findLCA(root->right , p, q);

                // if one of p or q is in leftsubtree and other is in right
                // then root it the LCA.
                if(l && r) {
                        return root;
                }
                // else if l is not null, l is LCA.
                else if(l) {
                        return l;
                } else {
                        return r;
                }
        }
}

当其中任何一个是其他人的直接孩子时,以下代码都会失败

treeNodePtr findLCA(treeNodePtr root, treeNodePtr p, treeNodePtr q) {

        // no root no LCA.
        if(!root) {
                return NULL;
        }

        // if either p or q is direct child of root then root is LCA.
        if(root->left==p || root->left==q || 
           root->right ==p || root->right ==q) {
                return root;
        } else {
                // get LCA of p and q in left subtree.
                treeNodePtr l=findLCA(root->left , p , q);

                // get LCA of p and q in right subtree.
                treeNodePtr r=findLCA(root->right , p, q);

                // if one of p or q is in leftsubtree and other is in right
                // then root it the LCA.
                if(l && r) {
                        return root;
                }
                // else if l is not null, l is LCA.
                else if(l) {
                        return l;
                } else {
                        return r;
                }
        }
}

代码在行动

Answer 2

尼克约翰逊是正确的,如果你没有父指针,你可以做的最好的O(n)时间复杂度算法.)对于该算法的简单递归版本,请参阅Kinding的帖子中的代码,该代码在O(n)时间内运行.

但请记住,如果您的节点有父指针,则可以使用改进的算法.对于所讨论的两个节点,通过从节点开始构造包含从根到节点的路径的列表,并且前面插入父节点.

所以对于你的例子中的8,你得到(显示步骤):{4},{2,4},{1,2,4}

对您所讨论的其他节点执行相同操作,导致(步骤未显示):{1,2}

现在比较您查找列表不同的第一个元素的两个列表,或者其中一个列表的最后一个元素,以先到者为准.

该算法需要O(h)时间,其中h是树的高度.在最坏的情况下,O(h)等价于O(n),但如果树是平衡的,那只是O(log(n)).它还需要O(h)空间.可能只使用恒定空间的改进版本,代码显示在CEGRD的帖子中

无论树是如何构造的,如果这将是您在树上执行多次而不在其间进行更改的操作,您可以使用其他算法,这些算法需要O(n)[线性]时间准备,但随后找到任何对只需要O(1)[常数]时间.有关这些算法的参考,请参阅Wikipedia上最低的共同祖先问题页面.(感谢Jason最初发布此链接)

Answer 3

这是JAVA中的工作代码

public static Node LCA(Node root, Node a, Node b) {
   if (root == null) {
       return null;
   }

   // If the root is one of a or b, then it is the LCA
   if (root == a || root == b) {
       return root;
   }

   Node left = LCA(root.left, a, b);
   Node right = LCA(root.right, a, b);

   // If both nodes lie in left or right then their LCA is in left or right,
   // Otherwise root is their LCA
   if (left != null && right != null) {
      return root;
   }

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

Answer 4

到目前为止给出的答案使用递归或存储,例如,内存中的路径.

如果你有一棵非常深的树,这两种方法都可能会失败.

这是我对这个问题的看法.当我们检查两个节点的深度(距离根的距离)时,如果它们相等,那么我们可以安全地从两个节点向上移动到共同的祖先.如果其中一个深度更大,那么我们应该从更深的节点向上移动而留在另一个节点中.

这是代码:

findLowestCommonAncestor(v,w):
  depth_vv = depth(v);
  depth_ww = depth(w);

  vv = v; 
  ww = w;

  while( depth_vv != depth_ww ) {
    if ( depth_vv > depth_ww ) {
      vv = parent(vv);
      depth_vv--;
    else {
      ww = parent(ww);
      depth_ww--;
    }
  }

  while( vv != ww ) {
    vv = parent(vv);
    ww = parent(ww);
  }

  return vv;    

该算法的时间复杂度为:O(n).该算法的空间复杂度为:O(1).

关于深度的计算,我们可以首先记住定义:如果v是root,则depth(v)= 0; 否则,深度(v)=深度(父(v))+ 1.我们可以如下计算深度:

depth(v):
  int d = 0;
  vv = v;
  while ( vv is not root ) {
    vv = parent(vv);
    d++;
  }
  return d;

Answer 5

嗯,这取决于你的二叉树的结构.假设您有一些方法可以在给定树根的情况下找到所需的叶节点 - 只需将其应用于两个值,直到您选择的分支发散为止.

如果您没有办法在给定根目录的情况下找到所需的叶子,那么您的唯一解决方案 - 无论是在正常操作中还是在找到最后一个公共节点 - 都是对树的强力搜索.

Answer 6

可以在以下网址找到: - http://goursaha.freeoda.com/DataStructure/LowestCommonAncestor.html

 tree_node_type *LowestCommonAncestor(
 tree_node_type *root , tree_node_type *p , tree_node_type *q)
 {
     tree_node_type *l , *r , *temp;
     if(root==NULL)
     {
        return NULL;
     }

    if(root->left==p || root->left==q || root->right ==p || root->right ==q)
    {
        return root;
    }
    else
    {
        l=LowestCommonAncestor(root->left , p , q);
        r=LowestCommonAncestor(root->right , p, q);

        if(l!=NULL && r!=NULL)
        {
            return root;
        }
        else
        {
        temp = (l!=NULL)?l:r;
        return temp;
        }
    }
}

Answer 7

Tarjan的离线最不常见的祖先算法足够好(参见维基百科).维基百科上的问题(最常见的共同祖先问题)还有很多.

Answer 8

我尝试使用 Java 中的说明性图片和工作代码，

http://tech.bragboy.com/2010/02/least-common-ancestor-without-using.html

Answer 9

找出两个节点的共同祖先: -

• 使用二进制搜索在树中查找给定节点Node1,并将此过程中访问的所有节点保存在一个数组中,如A1.时间 - O(logn),空格 - O(logn)
• 使用二进制搜索在树中查找给定的Node2,并将此过程中访问的所有节点保存在一个数组中,如A2.时间 - O(logn),空格 - O(logn)
• 如果A1列表或A2列表为空,则该节点之一不存在,因此没有共同的祖先.
• 如果A1列表和A2列表非空,则查看列表,直到找到不匹配的节点.一旦找到这样的节点,那么之前的节点就是共同的祖先.

这适用于二叉搜索树.