---

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

• 标签：树、并查集、二叉搜索树、记忆化搜索、数组、数学、分治、动态规划、二叉树、组合数学
• 难度：困难

题目链接

• 1569. 将子数组重新排序得到同一个二叉搜索树的方案数 - 力扣

题目大意

描述：给定一个 $1 \sim n$ 的排列 $nums$。用 $nums$ 构建一棵 BST：依次插入每个元素。

要求：返回有多少种不同的排列方式（保持初始排列的 $nums$ 本身也算一种），使得构建的 BST 与用 $nums$ 构建的 BST 相同。结果对 $10^9 + 7$ 取模。

说明：

• $1 \le nums.length \le 1000$。

示例：

• 示例 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]

解题思路

思路 1：分治 + 组合数

1. 核心思想

BST 的插入顺序影响树的结构。根节点是第一个插入的元素。

一旦根节点确定，左子树的元素集合和右子树的元素集合也随之确定。但左右子树的元素在排列中可以交错出现，只要保持各自内部的相对顺序即可（即左子树的插入顺序决定了左子树的构造，右子树同理）。

因此对根节点来说：

• 左右子树的元素可以交错排列，交错的方式数为 $C(len\_left + len\_right, len\_left)$（或 $C(n-1, len\_left)$）。
• 左右子树内部的排列方案数需要递归计算。
• 总方案数 = $C(n-1, len\_left) \times f(left) \times f(right)$。

2. 具体步骤

第 1 步：预计算组合数 $C[n][k]$（帕斯卡三角，$n \le 1000$）。

第 2 步：递归 $countWays(nums)$：

• 如果 $len(nums) \le 2$，返回 $1$（只有一个或两个元素时无法改变顺序）。
• 根 = $nums[0]$。
• 左子数组 $left = [x for x in nums[1:] if x < root]$。
• 右子数组 $right = [x for x in nums[1:] if x > root]$。
• 返回 $C[len(left)+len(right)][len(left)] \times countWays(left) \times countWays(right) \% MOD$。

3. 组合数的预计算

C = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n + 1):
    C[i][0] = C[i][i] = 1
    for j in range(1, i):
        C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD

4. 举例说明

以 $nums = [3,4,1,2]$ 为例：

根 $= 3$，左 $[1,2]$，右 $[4]$。

$C(3, 2) \times f([1,2]) \times f([4])$。

$f([1,2])$：根 $= 1$，左 $[]$，右 $[2]$。$C(1, 0) \times 1 \times 1 = 1$。
$f([4]) = 1$。

$C(3, 2) = 3$。总方案数 $= 3 \times 1 \times 1 = 3$。

验证排列：保持 BST 结构不变的可能排列：

• $[3,4,1,2]$（原始）
• $[3,1,4,2]$
• $[3,1,2,4]$

共 $3$ 种。

思路 1：代码

class Solution:
    def numOfWays(self, nums: List[int]) -> int:
        MOD = 10 ** 9 + 7
        n = len(nums)

        # 预计算组合数
        C = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(n + 1):
            C[i][0] = C[i][i] = 1
            for j in range(1, i):
                C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD

        def dfs(arr):
            if len(arr) <= 2:
                return 1
            root = arr[0]
            left = [x for x in arr[1:] if x < root]
            right = [x for x in arr[1:] if x > root]
            m = len(left) + len(right)
            return C[m][len(left)] * dfs(left) % MOD * dfs(right) % MOD

        # 减 1 排除原始排列自身（题目要求返回除去原始排列外的）
        # 但注意：描述有歧义，有的版本要求包含原始排列，有的不包含
        # 看题意：求"不同的排列方式"使得 BST 相同，保持初始排列的本身也算一种
        return (dfs(nums) - 1) % MOD

思路 1：复杂度分析

• 时间复杂度：$O(n^2)$，组合数预计算 $O(n^2)$，递归每次分区 $O(n)$。
• 空间复杂度：$O(n^2)$，组合数表。