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

Question

我有以下代码来查找最低的共同祖先(具有 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

问题

以下情况失败:

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.

有什么想法吗？

节点在哪里

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

Answer 1

如果 root 的 IData 不同于 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);
}