leetcode如何求将子数组重新排序得到同一个二叉查找树的方案数

这篇文章给大家分享的是有关leetcode如何求将子数组重新排序得到同一个二叉查找树的方案数的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。

给你一个数组 nums 表示 1 到 n 的一个排列。我们按照元素在 nums 中的顺序依次插入一个初始为空的二叉查找树（BST）。请你统计将 nums 重新排序后，统计满足如下条件的方案数：重排后得到的二叉查找树与 nums 原本数字顺序得到的二叉查找树相同。

比方说，给你 nums = [2,1,3]，我们得到一棵 2 为根，1 为左孩子，3 为右孩子的树。数组 [2,3,1] 也能得到相同的 BST，但 [3,2,1] 会得到一棵不同的 BST 。

请你返回重排 nums 后，与原数组 nums 得到相同二叉查找树的方案数。

由于答案可能会很大，请将结果对 10^9 + 7 取余数。

示例 1：

输入：nums = [2,1,3]

输出：1

解释：我们将 nums 重排， [2,3,1] 能得到相同的 BST 。没有其他得到相同 BST 的方案了。

示例 2：

输入：nums = [3,4,5,1,2]

输出：5

解释：下面 5 个数组会得到相同的 BST：

[3,1,2,4,5]

[3,1,4,2,5]

[3,1,4,5,2]

[3,4,1,2,5]

[3,4,1,5,2]

示例 3：

输入：nums = [1,2,3]

输出：0

解释：没有别的排列顺序能得到相同的 BST 。

示例 4：

输入：nums = [3,1,2,5,4,6]

输出：19

示例  5：

输入：nums = [9,4,2,1,3,6,5,7,8,14,11,10,12,13,16,15,17,18]

输出：216212978

解释：得到相同 BST 的方案数是 3216212999。将它对 10^9 + 7 取余后得到 216212978。

提示：

1 <= nums.length <= 1000

1 <= nums[i] <= nums.length

nums 中所有数 互不相同 

解题思路

1，这个题目是组合排列＋搜索树的组合题目

2，搜索树的性质，左节点<根<右节点

3，我们可以把树拆成左、根、右三部分

4，只要不改变左树内部元素的相对位置和右树内部元素的相对位置，搜索树不变

5，因此变成了排列组合问题

6，假设左树节点为m，右树为n

7,总个数为: C(len(m+n),len(m))*f(m)*f(n)

8,最后还需要把自己剪掉

代码实现

func numOfWays(nums []int) int {   return (getAllCount(nums)%1000000007-1+1000000007)%1000000007}
func split(nums[]int)([]int,[]int){    var l,r []int    for i:=1;i<len(nums);i++{        if nums[i]<nums[0]{            l=append(l,nums[i])        }else{            r=append(r,nums[i])        }    }    return l,r}
func getAllCount(nums []int) int{    if len(nums)<1{        return 1    }    l,r:=split(nums)    s:=way(len(l),len(r))    return (s*getAllCount(l)%1000000007)*getAllCount(r)%1000000007}
func way(l,r int)int{    sum:=1    for i:=1;i<=l;i++{        sum=(sum*(r+i)/i)%1000000007    }    return sum}

感谢各位的阅读！关于“leetcode如何求将子数组重新排序得到同一个二叉查找树的方案数”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！