问具有重复密钥的BST数

EN

重复的键对不同树的数目没有任何影响。每棵树都有一个不同的形状，所以你甚至不需要钥匙来区分它们。你可以把钥匙全部移开，而树仍然是不同的。

用简单的例子试试: 1,1,1。您仍然可以用以下键创建5个不同的BST：

    1      1      1      1      1  
   /      /      / \      \      \
  1      1      1   1      1      1
 /        \               /        \
1          1             1          1

为新的要求编辑：

如果左撇子必须严格地小于他们的父级，那么复制键就会形成一个链接列表，它的工作方式类似于一个节点，因为您不能在其中有任何左子节点。整个平等价值列表将只有一个形状，一个左子和一个右子：

    1
   / \
  0   1
       \
        1
         \
          2

因此，在这种情况下，您只需减去重复键的数量。

对于具有M个重复的N个键，即N唯一的键，有一些加泰罗尼亚(N)的方法来建立树。