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

public static Node LCA(Node root,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,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);
}