在二叉搜索树找到最低的共同祖先 [英] Find lowest common ancestor in Binary Search Tree

问题描述

我有下面的代码来找到最低的共同祖先（同时具有A和B的后裔最低节点）：

 公共静态节点LCA（根节点，节点A，节点b）
 {
如果（根== NULL）
返回NULL; 
 
如果（root.IData == || a.IData == root.IData b.IData）
返回根; 
 
如果（root.RightChild = NULL&放大器;！及（root.RightChild.IData == || a.IData == root.RightChild.IData b.IData））
返回根; 
 
如果（root.LeftChild = NULL&放大器;！及（root.LeftChild.IData == || a.IData == root.LeftChild.IData b.IData））
返回根; 
 
如果（root.IData> a.IData和放大器;&安培; root.IData> b.IData）
返回LCA（root.LeftChild，A，B）; 
否则如果（root.IData< a.IData&放大器;&安培; root.IData< b.IData）
返回LCA（root.RightChild，A，B）; 
，否则
返回根; 
} 
  

的

二叉搜索树是

  20 
 / \ 
 8月22日
 / \ 
 4月12日
 / \ 
 10 14 
  

问

有没有以下情况：

LCA（4,8）= 20，但应该是8

LCA（8,12）= 20，但应为8

LCA（8,23）= 20，非-existent数（23）作为参数。

有什么想法？

其中，节点是

 类节点
 {
公众诠释IData的{搞定;设置;} 
公共节点RightChild {搞定;设置;} 
公共节点LeftChild {搞定;设置;} 
} 
  

解决方案

 公共静态节点LCA（根节点，节点A，节点b）
 {
 
如果（根== NULL）
返回NULL; 
 
如果（root.IData> a.IData和放大器;&安培; root.IData> b.IData）
返回LCA（root.LeftChild，A，B）; 
如果（root.IData< a.IData&放大器;&安培; root.IData< b.IData）
返回LCA（root.RightChild，A，B）; 
 
返回根; 
} 
  

I've got the following code to find the lowest common ancestor (the lowest node that has both a and b as descendants):

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

    if (root.IData == a.IData || root.IData == b.IData)
        return root;

    if (root.RightChild != null && (root.RightChild.IData == a.IData || root.RightChild.IData == b.IData))
        return root;

    if (root.LeftChild != null && (root.LeftChild.IData == a.IData || root.LeftChild.IData == b.IData))
        return root;

    if (root.IData > a.IData && root.IData > b.IData)
        return LCA(root.LeftChild, a, b);
    else if (root.IData < a.IData && root.IData < b.IData)
        return LCA(root.RightChild, a, b);
    else
        return root;
}

The binary search tree is

                      20
                     /  \
                    8    22
                  /   \
                 4     12 
                      /  \
                    10    14

Question

It is failing for the following cases:

LCA (4, 8) = 20 but should be 8.

LCA (8, 12) = 20 but should be 8

LCA (8, 23) = 20, non-existent number (23) as parameter.

Any thoughts?

Where Node is

class Node
{
 public int IData {get; set;}
 public Node RightChild {get; set;}
 public Node LeftChild {get; set;}
}

解决方案

public static Node LCA(Node root, Node a, Node b)
{

    if (root == null)
        return null;

    if (root.IData > a.IData && root.IData > b.IData)
        return LCA(root.LeftChild, a, b);
    if (root.IData < a.IData && root.IData < b.IData)
        return LCA(root.RightChild, a, b);

    return root;
}

这篇关于在二叉搜索树找到最低的共同祖先的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！