use*_*033 6 algorithm tree permutation binary-search-tree data-structures
从集合{1,2,3,4,5,6,7}中的每个密钥排列生成(通过连续插入节点)BST.有多少个排列决定了两个高度的树木？
很长一段时间以来,我一直坚持这个简单的问题.任何暗示任何人.
那么答案是80.
考虑一下树的高度是多少？
- 需要以4为根,2为左子,6为右子等.
4根是怎么来的？
- 它需要是第一次插入.所以我们现在有一个数字,6仍然可以在排列中移动.
和？
- 第一次插入后,仍有6个位置,左边3个,右子树3个.这是6选择3 = 20选择.
怎么办？
- 对于左右子树,需要首先插入它们的根,然后子节点的顺序不会影响树 - 2,1,3和2,3,1给出相同的树.每个子树为2,左右子树为2*2 = 4.
所以？
总之:C(6,3)*2*2 = 20*2*2 = 80.
| 归档时间： |
|
| 查看次数： |
3052 次 |
| 最近记录： |