将子数组重新排序得到同一个二叉搜索树的方案数

难度: Hard

给你一个数组 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 。

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= nums.length
nums 中所有数 互不相同 。

Submission

运行时间: 64 ms

内存: 21.1 MB

MOD = 10**9+7
MX = 10**3
f = [1] * (MX+1)
for i in range(2, MX+1):
    f[i] = f[i-1] * i % MOD
g = [1] * (MX+1)
g[-1] = pow(f[-1], -1, MOD)
for i in range(MX, 1, -1):
    g[i-1] = g[i] * i % MOD
comb = lambda a, b: f[a] * g[b] * g[a-b] % MOD

class Solution:
    def numOfWays(self, nums: List[int]) -> int:
        ans = 1
        def dfs(arr):
            nonlocal ans
            if len(arr) <= 1:
                return 1
            rt = arr[0]
            lt, gt = [], []
            for x in arr[1:]:
                if x < rt:
                    lt.append(x)
                else:
                    gt.append(x)
            ans = ans * comb(len(arr)-1, len(lt)) % MOD
            dfs(lt)
            dfs(gt)
        dfs(nums)
        return (ans - 1) % MOD

Explain

此题解采用递归的方式来模拟 BST 的构建过程。首先，我们通过递归地分割数组，将其划分为左子树和右子树的元素。然后，我们使用组合数学来计算在给定左右子树大小的情况下，可以构建多少个相同结构的 BST。最后，我们将所有子树的方案数相乘得到最终结果。

时间复杂度: O(n)

空间复杂度: O(n)

MOD = 10**9+7
MX = 10**3
f = [1] * (MX+1)
for i in range(2, MX+1):
    f[i] = f[i-1] * i % MOD
g = [1] * (MX+1)
g[-1] = pow(f[-1], -1, MOD)
for i in range(MX, 1, -1):
    g[i-1] = g[i] * i % MOD
comb = lambda a, b: f[a] * g[b] * g[a-b] % MOD

class Solution:
    def numOfWays(self, nums: List[int]) -> int:
        ans = 1
        def dfs(arr):
            nonlocal ans
            if len(arr) <= 1:
                return 1
            rt = arr[0]
            lt, gt = [], []
            for x in arr[1:]:
                if x < rt:
                    lt.append(x)
                else:
                    gt.append(x)
            ans = ans * comb(len(arr)-1, len(lt)) % MOD
            dfs(lt)
            dfs(gt)
        dfs(nums)
        return (ans - 1) % MOD

Explore

在递归模拟BST的构建过程中，首先将数组的第一个元素视为根节点，然后遍历数组的其余部分来划分左右子树。具体来说，数组中小于根节点的元素会构成左子树，大于根节点的元素会构成右子树。通过这种方式，递归地对左子数组和右子数组进行同样的处理，从而实现整个数组的分割。这种方法确保了每次递归都能正确地按照BST的规则划分左右子树。

题解中使用递归时，每次都准确地计算了左右子树的大小，并使用组合数学计算了在给定左右子树大小下，可以构建相同结构的BST的数量。组合函数 `comb(a, b)` 用于计算从 `a` 个元素中选择 `b` 个元素的组合方式，其中 `a` 是当前节点的数量减去1（除去根节点），`b` 是左子树的节点数量。通过这种方式，即使在复杂的树结构中，也可以确保每个子问题的组合数计算是基于正确的左右子树大小，从而保证了整个递归过程的正确性。

在本题的解法中，`dfs`函数的主要目的是通过递归调用来更新全局变量`ans`，用于计算结果而非返回特定的函数值。`dfs`函数的返回值`1`在逻辑上表示对于单节点或空数组的情况，其构成的BST数量为1，这是一个基本情况。虽然这个返回值在递归过程中没有被直接利用，其存在主要是为了满足递归函数的定义，即每个分支都应有返回值，尽管这里的重点在于递归过程中的副作用（即更新`ans`）。

在题解中，`ans`初始值被设为1，而在整个递归过程中，我们计算的是包括给定数组在内的所有可能的BST重构方式的总数。因此，最终的`ans`值实际上包括了一个额外的计数——即原始数组自身。但题目要求的是“重新排序”数组以形成的BST数量，因此需要从计算结果中减去这个额外的1，即不包括未经任何变化的原始数组排列。这样，`(ans - 1) % MOD`确保了我们得到的是除原数组外的所有可能重构的数量，并且结果是在模`MOD`的条件下的。