给定一列不重复的数,依次插入一棵空树构成二叉搜索树,问若打乱这一列数的顺序,一共有多少种不同的打乱方式,可以得到一样的BST,递归分治思想
假设当前数列长l,那么第一个数字决定了root的位置,无法移动,之后的数字比root大的数和比root小的数的数量是一定的,假设有m个数比root大,n个数比root小(m+n+1=l)。那么打乱顺序还可以构成一样的BST的数量就是组合数C(m, m+n)。而左子树和右子树又将进行同样的计算。注意最终结果要-1(减去原本的那种排列方式)
1 #1569
2 #Runtime: 173 ms (Beats 71.74%)
3 #Memory: 21.8 MB (Beats 51.9%)
4
5 class Solution:
6 def numOfWays(self, nums: List[int]) -> int:
7 MOD = 10 ** 9 + 7
8
9 def cal(seq):
10 if not seq:
11 return 1
12 root = seq[0]
13 l_tree = [num for num in seq if num < root]
14 r_tree = [num for num in seq if num > root]
15 return math.comb(len(l_tree) + len(r_tree), len(l_tree)) * cal(l_tree) * cal(r_tree) % MOD
16 return (cal(nums) - 1) % MOD