3.2.9

上次更新:2019-06-27
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

比较简单,可以按照如下步骤解决:

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

全排列可以通过递归方式生成,方法类似于 DFS。
开始 pool 中存有所有的数,遍历 pool ,每次取一个数放入 path 中,然后递归选择下一个。

static 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! 棵二叉树之后,我们需要过滤掉结构相同的树。
我们可以把二叉树转换成数组表示(层序遍历即可),然后遍历数组进行比较。

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 库

上一题 下一题