计算产生相同 BST 的唯一节点序列的数量
Count number of unique node sequences producing the same BST
问题：
Given a particular sequence of up to 50 integers, which represent
nodes of a certain binary search tree (BST), how many permutations of
this sequence are there, which will also give rise to exactly the same
BST? Include the original sequence in your total count as 1 sequence.
For instance, answer = 6 for such a sequence [5,2,1,9,8]: [5,2,1,9,8]
(itself, the original sequence given), [5,9,8,2,1], [5,2,9,1,8],
[5,9,2,1,8], [5,2,9,8,1], [5,9,2,8,1]
假设给定的节点序列是我们将这些元素添加到 BST 中的顺序。
我们很容易看出，如果两个节点a和b属于两个不同的分支，那么添加a和b的顺序将不会影响最终的结构。
我们只需要确保先添加父项，然后再添加其子项。
例如 [5,2,1,9,8]：5 应该始终先添加。
只有两个选择：加2或加9
- 如果我们加2:1可以任意顺序加
- 类似的，如果我们加9: 8之后随时可以加
所以，现在我们有了从根 -> 叶移动的算法：
int numberOfWays (Node node) {
if(node is leaf) return 1;
int a = numberOfWays(node.left);
int b = numberOfWays(node.right);
int x = number of node in the left;
int y = number of node in the right;
//nCr is combination, so we can choose x places in total of x + y positions
return nCr(x+y,x) * a * b;
}
假设您有示例序列 [5,2,1,9,8]。第一个节点将成为二叉树的根节点，所以我们知道第一个节点必须是 5.
从此以后，所有小于5的节点都往左child，所有大于5的节点都往右child。
所以你可以递归地解决这个问题，计算左子树（由[2,1]组成）乘以[=的方法数26=] 生成右子树（由 [9,8] 组成）的方法数和 乘以 排序整数到达相对边的方法数。
示例代码
def nCr(n,r):
"""Return number of ways of choosing r objects from n"""
top, bottom = 1, 1
for i in xrange(r):
top *= n
n = n - 1
bottom *= r
r = r- 1
return top / bottom
def count_ways_to_make_bst(seq):
if len(seq)<=1:
return 1
num_remaining = len(seq) - 1
left = [r for r in seq[1:] if r>seq[0]]
right = [r for r in seq[1:] if r<seq[0]]
return count_ways_to_make_bst(left) * count_ways_to_make_bst(right) * nCr(num_remaining,len(left))
问题：
Given a particular sequence of up to 50 integers, which represent nodes of a certain binary search tree (BST), how many permutations of this sequence are there, which will also give rise to exactly the same BST? Include the original sequence in your total count as 1 sequence.
For instance, answer = 6 for such a sequence [5,2,1,9,8]: [5,2,1,9,8] (itself, the original sequence given), [5,9,8,2,1], [5,2,9,1,8], [5,9,2,1,8], [5,2,9,8,1], [5,9,2,8,1]
假设给定的节点序列是我们将这些元素添加到 BST 中的顺序。
我们很容易看出，如果两个节点a和b属于两个不同的分支，那么添加a和b的顺序将不会影响最终的结构。
我们只需要确保先添加父项，然后再添加其子项。
例如 [5,2,1,9,8]：5 应该始终先添加。
只有两个选择：加2或加9
- 如果我们加2:1可以任意顺序加
- 类似的，如果我们加9: 8之后随时可以加
所以，现在我们有了从根 -> 叶移动的算法：
int numberOfWays (Node node) {
if(node is leaf) return 1;
int a = numberOfWays(node.left);
int b = numberOfWays(node.right);
int x = number of node in the left;
int y = number of node in the right;
//nCr is combination, so we can choose x places in total of x + y positions
return nCr(x+y,x) * a * b;
}
假设您有示例序列 [5,2,1,9,8]。第一个节点将成为二叉树的根节点，所以我们知道第一个节点必须是 5.
从此以后，所有小于5的节点都往左child，所有大于5的节点都往右child。
所以你可以递归地解决这个问题，计算左子树（由[2,1]组成）乘以[=的方法数26=] 生成右子树（由 [9,8] 组成）的方法数和 乘以 排序整数到达相对边的方法数。
示例代码
def nCr(n,r):
"""Return number of ways of choosing r objects from n"""
top, bottom = 1, 1
for i in xrange(r):
top *= n
n = n - 1
bottom *= r
r = r- 1
return top / bottom
def count_ways_to_make_bst(seq):
if len(seq)<=1:
return 1
num_remaining = len(seq) - 1
left = [r for r in seq[1:] if r>seq[0]]
right = [r for r in seq[1:] if r<seq[0]]
return count_ways_to_make_bst(left) * count_ways_to_make_bst(right) * nCr(num_remaining,len(left))