python - 有多少种方法可以构建一棵完美平衡的树？

Question

问题是，有多少种方法可以构建具有 15 个元素的完美平衡的二叉树？

一种可能是 8-4-12-2-6-10-14-1-3-5-7-9-11-13-15..

我的想法是编写一些代码来生成所有可能的排列(就像.. 15!)，然后删除不正确的排列。

正确的是 8 作为第一个元素，4 总是在 2 和 6 之前，2 总是在 1 和 3 之前，6 总是在 5 和 7 之前，依此类推。

但是类似perms2 = list(itertools.permutations([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15])) 导致内存错误。

有没有办法根据上述规则生成排列？

或者有更简单的方法来解决我的问题吗？

顺便说一句..

• 如果元素个数为1，则有1种方式
• 对于 3 个元素，有 2 种方式(2-1-3 或 2-3-1)
• 7 个元素有 80 种方法(根据我的代码并手动完成)

但这并没有帮助我得到某种公式..

编辑:这就是我所说的树:http://666kb.com/i/bz9znnpdj7etw0fo9.gif

Answer 1

正确的数字是 21964800。这是合适的整数序列:

http://oeis.org/A076615

基本上你递归地增加了可能性:在最低级别上，您可以在两种可能性之间进行选择，例如:2-1-3 和 2-3-1。在上面的级别上，您可以将两个较低层的选定顺序纠缠在(6 over 3)中 方式等等。