c# - 在二叉搜索树中找到最低的共同祖先

我有以下代码来查找最低的公共(public)祖先(具有 a 和 b 作为后代的最低节点):

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;
}

二叉搜索树是

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

问题
它在以下情况下失败:

有什么想法吗？
节点在哪里

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

最佳答案

如果 IData 的 root 与 a 和 b 都不同，但 root 的一个子代与两者之一具有相同的 IData ，则返回 root ，但根据您的定义，如果两个节点都在同一个子树中。由于您还想检查两个节点是否实际上都在树中，因此必须在任何返回之前执行该检查。

public static Node LCA(Node root, Node a, Node b)
{
    if (root == null) return null;
    // what if a == null or b == null ?
    Node small, large, current = root;
    if (a.IData < b.IData)
    {
        small = a;
        large = b;
    }
    else
    {
        small = b;
        large = a;
    }
    if (large.IData < current.IData)
    {
        do
        {
            current = current.LeftChild;
        }while(current != null && large.IData < current.IData);
        if (current == null) return null;
        if (current.IData < small.IData) return LCA(current,small,large);
        // if we get here, current has the same IData as one of the two, the two are
        // in different subtrees, or not both are in the tree
        if (contains(current,small) && contains(current,large)) return current;
        // at least one isn't in the tree, return null
        return null;
    }
    else if (current.IData < small.IData)
    {
        // the symmetric case, too lazy to type it out
    }
    else // Not both in the same subtree
    {
        if (contains(current,small) && contains(current,large)) return current;
    }
    return null; // at least one not in tree
}

public static bool contains(Node root, Node target)
{
    if (root == null) return false;
    if (root.IData == target.IData) return true;
    if (root.IData < target.IData) return contains(root.RightChild,target);
    return contains(root.LeftChild,target);
}

关于c# - 在二叉搜索树中找到最低的共同祖先，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8441331/