Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给定一列不重复的数,依次插入一棵空树构成二叉搜索树,问若打乱这一列数的顺序,一共有多少种不同的打乱方式,可以得到一样的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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理