3.2.9

3.2.9 #

解答 #

比较简单，可以按照如下步骤解决：

生成 n 个数。
生成这 n 个数的全排列。
生成 n! 棵二叉搜索树，取其中结构不同的部分。

全排列可以通过递归方式生成，方法类似于 DFS。

开始 pool 中存有所有的数，遍历 pool ，每次取一个数放入 path 中，然后递归选择下一个。

void Permutation(List<int> pool, List<int> path, List<int[]> result)
{
    if (pool.Count == 0)
    {
        result.Add(path.ToArray());
        return;
    }

    for (var i = 0; i < pool.Count; i++)
    {
        var item = pool[i];
        path.Add(item);
        pool.RemoveAt(i);
        Permutation(pool, path, result);
        pool.Insert(i, item);
        path.Remove(item);
    }
}

有了 n! 棵二叉树之后，我们需要过滤掉结构相同的树。

我们可以把二叉树转换成数组表示（层序遍历即可），然后遍历数组进行比较。

public static bool IsStructureEqual<TKeyA, TValueA, TKeyB, TValueB>(Bst<TKeyA, TValueA> a, Bst<TKeyB, TValueB> b) 
    where TKeyA : IComparable<TKeyA> 
    where TKeyB : IComparable<TKeyB>
{
    var treeA = a.ToArray();
    var treeB = b.ToArray();

    if (treeA.Length != treeB.Length)
        return false;
    for (var i = 0; i < treeA.Length; i++)
    {
        if (treeA[i] == null && treeB[i] == null)
            continue;
        if (treeA[i] != null && treeB[i] != null)
            continue;
        return false;
    }

    return true;
}

结果如下：

n=2

n=3

n=4

n=5

n=6

另请参阅 #

BinarySearchTree 库