如果n个顶点的键不同于Catalan number给出的BST的数量 . 但是，如果某些元素重复，我们如何计算BST的数量？
我天真的想法，如果我们在n中有k个相等的元素，那么我们应该在k上划分加泰罗尼亚数字！（k个元素的排列） . 但是如果我们在最简单的例子（BST构建在[1,1,1]上）检查它，我们就会意识到这是错误的想法 .
那么，当我们计算BST的数量时，我们应该如何考虑重复的密钥？
What is BST in my question: 二叉树，其中左子节点中的所有键都小于root子节点，右子节点中的所有键都比root中的键更重要或等于 .
1 回答
重复的键对不同树的数量没有任何影响 . 每棵树都有一个独特的形状，所以你甚至不需要键来区分它们 . 你可以完全删除密钥，树木仍然会有所不同 .
试着用你的简单例子：[1,1,1] . 你仍然可以用这些键制作5个不同的BST：
编辑新要求：
如果左边的孩子必须严格小于他们的父母，那么重复的密钥就形成一个链接列表，就像单个节点一样，因为你不能有任何左边的孩子 . 整个相等值列表只有一个形状，一个是左子，一个是右子：
因此，在这种情况下，您只需减去重复键的数量即可 .
对于具有M个重复的N个密钥，即N-M个唯一密钥，存在用于制作树的加泰罗尼亚（N-M）方式 .