給定一列不重復(fù)的數(shù)，依次插入一棵空樹構(gòu)成二叉搜索樹，問若打亂這一列數(shù)的順序，一共有多少種不同的打亂方式，可以得到一樣的BST，遞歸分治思想
假設(shè)當(dāng)前數(shù)列長l，那么第一個(gè)數(shù)字決定了root的位置，無法移動(dòng)，之后的數(shù)字比root大的數(shù)和比root小的數(shù)的數(shù)量是一定的，假設(shè)有m個(gè)數(shù)比root大，n個(gè)數(shù)比root小（m+n+1=l）。那么打亂順序還可以構(gòu)成一樣的BST的數(shù)量就是組合數(shù)C(m, m+n)。而左子樹和右子樹又將進(jìn)行同樣的計(jì)算。注意最終結(jié)果要-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