在二分查找树中查找两个节点的最低共同祖先 - 有效

3 回答

• 0

  在二叉搜索树中搜索最低共同祖先比这更简单：观察LCA是第一次搜索项目A和项目B的节点 .

  从根开始，同时搜索A和B.只要两次搜索都指向同一方向，请继续搜索 . 到达节点后，搜索A和B会将您带到不同的子树，您知道当前节点是LCA .

  回复于 2024-05-02T19:59:58+08:00
• 2

  大型二元搜索树底部的节点可以具有接近它的有序后继节点，例如，如果它是节点的左子节点，则其有序后继节点是其父节点 .

  从根的不同子节点下降的两个节点将根作为它们最不共同的祖先，无论它们在哪里，所以我相信你的算法得到了这种情况是错误的 .

  这是对有效LCA算法（给定时间来构建预备数据结构）的讨论，在http://en.wikipedia.org/wiki/Lowest_common_ancestor，带有指向代码的指针 .

  找到LCA的低效但简单的方法如下：在树中保留从子节点到父节点的指针以及每个节点的深度的注释 . 给定两个节点，如果相同，则从最深的节点向上移动直到深度 . 如果您指向另一个节点，则它是LCA . 否则，从每个节点向上移动一步并再次检查，依此类推，直到您在LCA会面 .

  回复于 2024-05-02T19:59:58+08:00
• 8

  Finding LCA of BST is straight:

  找到不同侧存在node1和node2的节点 . 但是如果node1是node2的祖先，那么我们将不得不返回node1 . 下面的代码实现了这个算法 .

  ---

  TreeNode<K> commonAncestor(TreeNode t, K k1, K k2){
          if(t==null) return null;
          while(true)
          {
             int c1=t.k.compareTo(k1);
             int c2=t.k.compareTo(k2);
             if(c1*c2<=0)
             {
                 return t;
             }
             else
             {
                 if(c1<0)
                 {
                     t = t.right;
                 }
                 else
                 {
                     t = t.left;
                 }
             }
          }
      }
  

  回复于 2024-05-02T19:59:58+08:00