在二叉树中查找共同的祖先

10 回答

• 6

  嗨这将返回最低的祖先节点值，其中树的根和val1，val2 - >节点的数据值正在传递

  int CommonAncestor(node *root, int val1,int val2) 
  {
  
      if(root == NULL || (! root->left && ! root->right  )
          return false;
  
          while(root)
          {
              if(root->data < val1 && root->data < val2)
               {
                  root = root->left;
               }
               else if(root->data > val1 && root->data > val2)
              {
                  root= root->right;
              }
              else
                return root->data;      
          }
  }
  

  回复于 2024-04-26T18:05:57+08:00
• 2

  也许愚蠢的方法：

  生成从每个节点到根的路径，将其存储为“L”和“R”字符串 .

  反转这些字符串 . 采用最长的公共前缀 - 您现在拥有共同祖先的路径 .

  回复于 2024-04-26T18:05:57+08:00
• 0

  在两个随机节点上设置指针 . 通过遍历顶部并计算距根节点的距离来查找每个节点的深度 . 然后再次将指针设置在两个节点上 . 对于更深的节点，遍历直到两个指针都处于相同的深度 . 然后遍历两个节点，直到指针指向同一节点 . 那是祖先节点 .

  通过“遍历”我只是意味着将指针移动到当前节点的父节点 .

  Edit to clarify: 关键的想法是，当两个节点处于相同的深度时，您可以通过简单的遍历非常快地找到共同的父节点 . 所以你爬到下面的一个直到两个都在相同的深度，然后你走了 . 抱歉，我没有编写代码，但该算法应该回答您的问题 .

  Edit again: 我的方法在O（log（n））时间和O（1）内存中运行 .

  Another edit: O（log（n））在 balancer 树中 . 对于不 balancer 树，最坏情况性能是O（n） . 谢谢@DaveCahill

  回复于 2024-04-26T18:05:57+08:00
• 3

  我想你可以同时搜索两个节点;搜索发散的点是共同的祖先 .

  commonAncestor tree a b:
    value := <value of node 'tree'>
    if (a < value) && (b < value)
    then commonAncestor (left tree) a b
    else if (a > value) && (b > value)
    then commonAncestor (right tree) a b
    else tree
  

  有趣的是，这种方法可以扩展到两个以上的节点（检查所有节点是否在 tree 的左侧，等等）

  回复于 2024-04-26T18:05:57+08:00
• 0

  进行级别订单遍历，对于我们遇到的每个节点，我们检查其子级 . 如果它们是提供的随机节点，则找到祖先节点 .

  EDIT1:

  这是一个大纲

  struct _node {
     my_type data;
     struct _node *left;
     struct _node *right;
  }
  
  q = queue_create ();
  queue_insert (q, head);
  temp = head;
  while (!empty (q))
  {
      temp = queue_remove (q);
   if (
        (temp->left == my_random_node_1) && (head->right == my_random_node_2) ||
        (temp->left == my_random_node_2) && (head->right == my_random_node_1)
      )
      {
         /* temp is the common parent of the two target notes */
         /* Do stuffs you need to do */
      }
  
      /* Enqueue the childs, so that in successive iterations we can
       * check them, by taking out from the queue
       */
      push (q, temp->left);
      push (q, temp->right);
  }
  

  ---

  UPDATE

  先前的算法将只找到共同的父母（直接祖先），因此如果两个随机选择的节点如果不是普通父母的孩子，则不会找到答案 .

  以下算法将找到共同的祖先，而不仅仅是父母 .

  我认为以下算法将起作用：

  对二叉树进行后序遍历，找到随机节点1 r1 ，如果我们找到它然后在状态变量中将其标记为状态1，并继续查找第二个节点，如果找到则更新状态变量说明两点，并停止搜索并返回 . 状态变量应该由每个节点传递给它的父节点（递归地） . 在状态2中遇到状态变量的第一个节点是共同的祖先 .

  算法的实现如下：

  int postorder (node *p, int r1, int r2)
  {
    int x = 0; /* The state variable */
    if (p->data == TERMINAL_VAL)
      return x;
  
    /* 0x01 | 0x02 = 0x03 threfore 
     * state one is when x = 0x01 or x = 0x02
     * state two is when x = 0x03
     */
    if (p->data == r1)
      x |= 0x01;
    else if (p->data == r2)
      x |= 0x02;
  
    /* if we have x in state two, no need to search more
     */
    if (x != 0x03)
      x |= postorder (p->left, r1, r2);
    if (x != 0x03)
      x |= postorder (p->right, r1, r2);
  
    /* In this node we are in state two, print node if this node
     * is not any of the two nodes r1 and r2. This makes sure that
     * is one random node is an ancestor of another random node
     * then it will not be printed instead its parent will be printed
     */
    if ((x == 0x03) && (p->data != r1) && (p->data != r2))
    {
     printf ("[%c] ", p->data);
     /* set state variable to 0 if we do not want to print 
      * the ancestors of the first ancestor 
      */
     x = 0;
    }
  
    /* return state variable to parent
     */    
    return x;
  }
  

  我认为这将正常工作，但我仍然要证明算法的正确性 . 有一个缺点，即如果一个节点是另一个节点的子节点，那么它将仅打印作为另一个节点的父节点的节点，而不是打印它们的父节点 . 如果随机节点之一是另一个随机节点的祖先，那么它将打印其父节点而不是打印祖先随机节点 . 在其中一个随机节点是根节点的情况下，它将不打印任何内容，因为它始终是另一个随机节点的祖先，因此它们的共同祖先不存在 . 在这种特殊情况下，该函数将在 main 中返回 0x03 并且可以检测到它 .

  由于该算法进行后序遍历，因此它需要O（n）执行时间，因此需要O（n）存储器 . 此外，一旦找到两个节点，搜索就会停止，节点越浅，搜索结束的速度越快 .

  UPDATE

  以下是一些模式讨论：How to find the lowest common ancestor of two nodes in any binary tree?

  回复于 2024-04-26T18:05:57+08:00
• 7

  这个问题已得到很好的研究，并且已知的算法可以在线性时间内解决它 . This paper 描述了可用于解决它的许多不同方法 . 承认它是一个研究论文，所以算法有点棘手，但它描述的一些方法实际上是非常可行的 .

  回复于 2024-04-26T18:05:57+08:00
• 1

  @Above，这不起作用，因为你假设两个节点都是某个特定节点的直接子节点...

  8
       10           12
   7
  

  我把节点分为7和12，答案必须是8.让我们这样做

  find(root, d1, d2, n1=null, n2=null)
       {
            if(n1 && n2) return;
            if(!root) return;
  
            else  if(root -> d == d1 ) n1 = root;
            else  if(root -> d == d2 ) n2 = root;                     
            find(root->left, d1, d2, n1, n2);
            find(root->right, d1, d2, n1, n2);
       }
  
       LCA(root, d1, d2)
       {
           node *n1=null, *n2=null;
           find(root, d1, d2, n1, n2);
           if(n1 == null || n2 == null )error 'nodes not present' exit(0);
           findIntersect(n1, n2); 
       }
       findInterSect(node *n1, node *n2)
       {
          l1 = length(n1);
          l2 = length(n2);
          node *g = n2, *l = n1;
          diff = abs(l1 - l2);
          if(l1>l2) g = n1 l =n2 
          while(diff) g = g->parent; diff--;
          // now both nodes are at same level
          while(g != l) g= g->parent, l = l->parent;
       }
  

  回复于 2024-04-26T18:05:57+08:00
• 0

  伪代码：

  node *FindCommonAncestor(node *root, node *node1, node *node2) {
    node *current = node1;
    node_list temp_list;
    temp_list.add(current);
    while (current != root) {
      current = current.parent;
      temp_list.add(current);
    }
    current = node2;
    while (current not in temp_list) {
      current = current.parent;
    }
    return current;
  }
  

  如果节点肯定是同一棵树的一部分，那么它们肯定会有一个共同的祖先（即使它是最坏情况下的根） . 所以它总是会终止，并且没有错误的条件需要担心 .

  第一个循环运行n次，其中n是node1的深度，因此它是O（n） . 第二个循环运行m次，其中m在node2的深度 . 查找临时列表是（最坏的）n . 所以第二个循环是O（m * n），它占主导地位，所以函数在O（m * n）中运行 .

  如果为临时空间而不是列表使用良好的设置数据结构（例如，哈希表），则可以将查找切换为（通常）O（1），而不会增加将节点添加到temp的成本 . 这将我们的功能时间减少到O（m） .

  空间要求是O（n）两种方式 .

  由于我们不提前知道n和m，所以让我们根据树中节点的总数来说：S . 如果树是 balancer 的，那么n和m都是由log_2（S）限定的，所以运行时间为O（log_2（S）^ 2） . Log_2非常强大，所以在我担心2的强大之前，S必须变得非常大 . 如果树不 balancer ，那么我们就失去了log_2（树可能实际上退化为链表） . 因此绝对最坏的情况（当一个节点是根节点而另一个节点是完全退化树的叶子时）是O（S ^ 2） .

  回复于 2024-04-26T18:05:57+08:00
• 0

  • 预订单遍历，除非满足任何1个节点并保存现在访问过的节点 .

  • 按顺序遍历，在满足任何1个（提供的两个节点中）节点时开始保存节点，并保存列表直到满足下一个节点 .

  • post order traversal，当两个节点都被访问时开始保存节点...

  A
  

  B                  C
  

  D       E          F       G
  

  H   I   J   K      L   M   N   O
  

  假设H和E是两个随机节点 .

  • ABDH

  • HDIBJE

  • EBLMENOGCA

  找到这三个中常见的第一个节点......

  回复于 2024-04-26T18:05:57+08:00
• 0

  以下是c＃（ . net）中的两种方法（均在上面讨论过）供参考：

  • 在二叉树中查找LCA的递归版本（O（N） - 最多访问每个节点）（解决方案的主要点是LCA是二叉树中的唯一节点，其中两个元素都位于子树的任一侧（左侧和正确）是LCA . (b) 并且无论哪个节点出现在任何一方并不重要 - 最初我试图保留该信息，显然递归函数变得如此令人困惑 . 一旦我意识到它，它变得非常优雅 .

  • 搜索两个节点（O（N）），并跟踪路径（使用额外的空间 - 所以，＃1可能更好，即使二进制树很 balancer ，因为额外的内存消耗将只是空间可能是微不足道的在O（log（N）） .

  以便比较路径（与接受的答案类似 - 但是通过假设二进制树节点中不存在指针节点来计算路径）

  • 仅为完成（与问题无关），BST中的LCA（O（log（N））

  • 测试

  Recursive:

  private BinaryTreeNode LeastCommonAncestorUsingRecursion(BinaryTreeNode treeNode, 
              int e1, int e2)
          {
              Debug.Assert(e1 != e2);
  
              if(treeNode == null)
              {
                  return null;
              }
              if((treeNode.Element == e1)
                  || (treeNode.Element == e2))
              {
                  //we don't care which element is present (e1 or e2), we just need to check 
                  //if one of them is there
                  return treeNode;
              }
              var nLeft = this.LeastCommonAncestorUsingRecursion(treeNode.Left, e1, e2);
              var nRight = this.LeastCommonAncestorUsingRecursion(treeNode.Right, e1, e2);
              if(nLeft != null && nRight != null)
              {
                  //note that this condition will be true only at least common ancestor
                  return treeNode;
              }
              else if(nLeft != null)
              {
                  return nLeft;
              }
              else if(nRight != null)
              {
                  return nRight;
              }
              return null;
          }
  

  where above private recursive version is invoked by following public method:

  public BinaryTreeNode LeastCommonAncestorUsingRecursion(int e1, int e2)
          {
              var n = this.FindNode(this._root, e1);
              if(null == n)
              {
                  throw new Exception("Element not found: " + e1);
              }
              if (e1 == e2)
              {   
                  return n;
              }
              n = this.FindNode(this._root, e2);
              if (null == n)
              {
                  throw new Exception("Element not found: " + e2);
              }
              var node = this.LeastCommonAncestorUsingRecursion(this._root, e1, e2);
              if (null == node)
              {
                  throw new Exception(string.Format("Least common ancenstor not found for the given elements: {0},{1}", e1, e2));
              }
              return node;
          }
  

  Solution by keeping track of paths of both nodes:

  public BinaryTreeNode LeastCommonAncestorUsingPaths(int e1, int e2)
          {
              var path1 = new List<BinaryTreeNode>();
              var node1 = this.FindNodeAndPath(this._root, e1, path1);
              if(node1 == null)
              {
                  throw new Exception(string.Format("Element {0} is not found", e1));
              }
              if(e1 == e2)
              {
                  return node1;
              }
              List<BinaryTreeNode> path2 = new List<BinaryTreeNode>();
              var node2 = this.FindNodeAndPath(this._root, e2, path2);
              if (node1 == null)
              {
                  throw new Exception(string.Format("Element {0} is not found", e2));
              }
              BinaryTreeNode lca = null;
              Debug.Assert(path1[0] == this._root);
              Debug.Assert(path2[0] == this._root);
              int i = 0;
              while((i < path1.Count)
                  && (i < path2.Count)
                  && (path2[i] == path1[i]))
              {
                  lca = path1[i];
                  i++;
              }
              Debug.Assert(null != lca);
              return lca;
          }
  

  where FindNodeAndPath is defined as

  private BinaryTreeNode FindNodeAndPath(BinaryTreeNode node, int e, List<BinaryTreeNode> path)
          {
              if(node == null)
              {
                  return null;
              }
              if(node.Element == e)
              {
                  path.Add(node);
                  return node;
              }
              var n = this.FindNodeAndPath(node.Left, e, path);
              if(n == null)
              {
                  n = this.FindNodeAndPath(node.Right, e, path);
              }
              if(n != null)
              {
                  path.Insert(0, node);
                  return n;
              }
              return null;
          }
  

  BST（LCA） - 无关（仅供完成参考）

  public BinaryTreeNode BstLeastCommonAncestor(int e1, int e2)
          {
              //ensure both elements are there in the bst
              var n1 = this.BstFind(e1, throwIfNotFound: true);
              if(e1 == e2)
              {
                  return n1;
              }
              this.BstFind(e2, throwIfNotFound: true);
              BinaryTreeNode leastCommonAcncestor = this._root;
              var iterativeNode = this._root;
              while(iterativeNode != null)
              {
                  if((iterativeNode.Element > e1 ) && (iterativeNode.Element > e2))
                  {
                      iterativeNode = iterativeNode.Left;
                  }
                  else if((iterativeNode.Element < e1) && (iterativeNode.Element < e2))
                  {
                      iterativeNode = iterativeNode.Right;
                  }
                  else
                  {
                      //i.e; either iterative node is equal to e1 or e2 or in between e1 and e2
                      return iterativeNode;
                  }
              }
              //control will never come here
              return leastCommonAcncestor;
          }
  

  Unit Tests

  [TestMethod]
          public void LeastCommonAncestorTests()
          {
              int[] a = { 13, 2, 18, 1, 5, 17, 20, 3, 6, 16, 21, 4, 14, 15, 25, 22, 24 };
              int[] b = { 13, 13, 13, 2, 13, 18, 13, 5, 13, 18, 13, 13, 14, 18, 25, 22};
              BinarySearchTree bst = new BinarySearchTree();
              foreach (int e in a)
              {
                  bst.Add(e);
                  bst.Delete(e);
                  bst.Add(e);
              }
              for(int i = 0; i < b.Length; i++)
              {
                  var n = bst.BstLeastCommonAncestor(a[i], a[i + 1]);
                  Assert.IsTrue(n.Element == b[i]);
                  var n1 = bst.LeastCommonAncestorUsingPaths(a[i], a[i + 1]);
                  Assert.IsTrue(n1.Element == b[i]);
                  Assert.IsTrue(n == n1);
                  var n2 = bst.LeastCommonAncestorUsingRecursion(a[i], a[i + 1]);
                  Assert.IsTrue(n2.Element == b[i]);
                  Assert.IsTrue(n2 == n1);
                  Assert.IsTrue(n2 == n);
              }
          }
  

  回复于 2024-04-26T18:05:57+08:00