Hard

题目描述

给定一个数组 nums 表示从 1 到 n 的整数的一个排列。我们将按顺序将 nums 的元素插入到一个初始为空的二叉搜索树（BST）中来构造 BST。找出重新排列 nums 的不同方法数，使得构造的 BST 与从原始数组 nums 形成的 BST 相同。

例如，给定 nums = [2,1,3]，我们将有 2 作为根，1 作为左子节点，3 作为右子节点。数组 [2,3,1] 也会产生相同的 BST，但 [3,2,1] 会产生不同的 BST。

返回重新排列 nums 的方法数，使得形成的 BST 与从 nums 形成的原始 BST 相同。

由于答案可能很大，请返回答案模 10^9 + 7。

示例 1：

输入: nums = [2,1,3]
输出: 1
解释: 我们可以将 nums 重新排列为 [2,3,1]，这将产生相同的 BST。没有其他方法重新排列 nums 来产生相同的 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
解释: 没有其他 nums 的排序会产生相同的 BST。

约束条件：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= nums.length
  • nums 中的所有整数都是不同的

解题思路

这是一道经典的分治 + 组合数学问题。

核心思路：

  1. BST的构建规律：第一个元素总是根节点，小于根的元素会进入左子树，大于根的元素会进入右子树
  2. 要保持BST结构不变，根节点必须保持在第一位，但左右子树内的元素可以重新排列

分治策略：

  • 以根节点为分界，将数组分为左子树序列和右子树序列
  • 递归计算左右子树各自的排列方案数
  • 使用组合数学计算合并方案数：在总共 left_size + right_size 个位置中选择 left_size 个位置放左子树元素

组合数计算： 如果左子树有 m 个元素，右子树有 n 个元素，那么合并方案数为 C(m+n, m)，表示从 m+n 个位置中选择 m 个位置放左子树元素。

实现细节：

  • 预计算组合数避免重复计算
  • 使用递归处理子树
  • 结果需要模 10^9 + 7

时间复杂度主要在于递归分治和组合数计算，整体为 O(n²)。

代码实现

class Solution {
public:
    int numOfWays(vector<int>& nums) {
        int n = nums.size();
        if (n <= 2) return 0;
        
        const int MOD = 1e9 + 7;
        
        // 预计算组合数
        vector<vector<long long>> C(n + 1, vector<long long>(n + 1, 0));
        for (int i = 0; i <= n; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
            }
        }
        
        function<long long(vector<int>&)> dfs = [&](vector<int>& arr) -> long long {
            if (arr.size() <= 2) return 1;
            
            int root = arr[0];
            vector<int> left, right;
            
            for (int i = 1; i < arr.size(); i++) {
                if (arr[i] < root) {
                    left.push_back(arr[i]);
                } else {
                    right.push_back(arr[i]);
                }
            }
            
            long long leftWays = dfs(left);
            long long rightWays = dfs(right);
            
            return (((leftWays * rightWays) % MOD) * C[left.size() + right.size()][left.size()]) % MOD;
        };
        
        return (dfs(nums) - 1 + MOD) % MOD;
    }
};

class Solution:
    def numOfWays(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 2:
            return 0
        
        MOD = 10**9 + 7
        
        # 预计算组合数
        C = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(n + 1):
            C[i][0] = 1
            for j in range(1, i + 1):
                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]
            
            left_ways = dfs(left)
            right_ways = dfs(right)
            
            return (left_ways * right_ways * C[len(left) + len(right)][len(left)]) % MOD
        
        return (dfs(nums) - 1) % MOD

public class Solution {
    public int NumOfWays(int[] nums) {
        int n = nums.Length;
        if (n <= 2) return 0;
        
        const int MOD = 1000000007;
        
        // 预计算组合数
        long[,] C = new long[n + 1, n + 1];
        for (int i = 0; i <= n; i++) {
            C[i, 0] = 1;
            for (int j = 1; j <= i; j++) {
                C[i, j] = (C[i-1, j-1] + C[i-1, j]) % MOD;
            }
        }
        
        long Dfs(List<int> arr) {
            if (arr.Count <= 2) return 1;
            
            int root = arr[0];
            List<int> left = new List<int>();
            List<int> right = new List<int>();
            
            for (int i = 1; i < arr.Count; i++) {
                if (arr[i] < root) {
                    left.Add(arr[i]);
                } else {
                    right.Add(arr[i]);
                }
            }
            
            long leftWays = Dfs(left);
            long rightWays = Dfs(right);
            
            return (leftWays * rightWays % MOD * C[left.Count + right.Count, left.Count]) % MOD;
        }
        
        return (int)((Dfs(new List<int>(nums)) - 1 + MOD) % MOD);
    }
}

var numOfWays = function(nums) {
    const n = nums.length;
    if (n <= 2) return 0;
    
    const MOD = 1e9 + 7;
    
    // 预计算组合数
    const C = Array(n + 1).fill().map(() => Array(n + 1).fill(0));
    for (let i = 0; i <= n; i++) {
        C[i][0] = 1;
        for (let j = 1; j <= i; j++) {
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }
    }
    
    function dfs(arr) {
        if (arr.length <= 2) return 1;
        
        const root = arr[0];
        const left = [];
        const right = [];
        
        for (let i = 1; i < arr.length; i++) {
            if (arr[i] < root) {
                left.push(arr[i]);
            } else {
                right.push(arr[i]);
            }
        }
        
        const leftWays = dfs(left);
        const rightWays = dfs(right);
        
        return (leftWays * rightWays % MOD * C[left.length + right.length][left.length]) % MOD;
    }
    
    return (dfs(nums) - 1 + MOD) % MOD;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n²)
空间复杂度O(n²)

说明：

  • 时间复杂度：O(n²) - 主要由预计算组合数 O(n²) 和递归分治 O(n) 组成
  • 空间复杂度：O(n²) - 组合数数组占用 O(n²) 空间，递归调用栈深度 O(n)