What is the primary approach to solving the Number of Ways to Reorder Array to Get Same BST problem?

The primary approach is to recursively divide the array into subarrays while maintaining the binary search tree properties, then apply combinatorics to count valid reorderings.

How does the divide and conquer pattern apply to this problem?

Divide and conquer is used to break the problem into smaller subproblems by recursively constructing the BST and counting valid reorderings within each subtree.

What role does dynamic programming play in solving this problem?

Dynamic programming is used to store intermediate results and avoid redundant calculations, speeding up the solution by reusing previously computed values.

How do binomial coefficients help in counting valid reorderings of the array?

Binomial coefficients are used to calculate how many ways elements can be reordered within a subtree while preserving the binary search tree structure.

What happens if there are no reorderings that can form the same BST?

If no reorderings are possible, the function should return 0, indicating that no valid permutations exist that maintain the same BST structure.

#1569

Hard

auto_awesome二分·树·traversal

LeetCode 题解工作台

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

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

数组数学分治动态规划树

题目描述

给你一个数组 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⁹ + 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 中所有数 互不相同 。

lightbulb

解题思路

方法一：组合计数 + 递归

我们设计一个函数 $dfs(nums)$ ，它的功能是计算以 $nums$ 为节点构成的二叉搜索树的方案数。那么答案就是 $dfs(nums)-1$ ，因为 $dfs(nums)$ 计算的是以 $nums$ 为节点构成的二叉搜索树的方案数，而题目要求的是重排后与原数组 $nums$ 得到相同二叉搜索树的方案数，因此答案需要减去一。

接下来，我们来看一下 $dfs(nums)$ 的计算方法。

对于一个数组 $nums$ ，它的第一个元素是根节点，那么它的左子树的元素都小于它，右子树的元素都大于它。因此，我们可以将数组分为三部分，第一部分是根节点，第二部分是左子树的元素，记为 $left$ ，第三部分是右子树的元素，记为 $right$ 。那么，左子树的元素个数为 $m$ ，右子树的元素个数为 $n$ ，那么 $left$ 和 $right$ 的方案数分别为 $dfs(left)$ 和 $dfs(right)$ 。我们可以在数组 $nums$ 的 $m + n$ 个位置中选择 $m$ 个位置放置左子树的元素，剩下的 $n$ 个位置放置右子树的元素，这样就能保证重排后与原数组 $nums$ 得到相同二叉搜索树。因此， $dfs(nums)$ 的计算方法为：

dfs(nums) = C_{m+n}^m \times dfs(left) \times dfs(right)

其中 $C_{m+n}^m$ 表示从 $m + n$ 个位置中选择 $m$ 个位置的方案数，我们可以通过预处理得到。

注意答案的取模运算，因为 $dfs(nums)$ 的值可能会很大，所以我们需要在计算过程中对每一步的结果取模，最后再对整个结果取模。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 是数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def numOfWays(self, nums: List[int]) -> int:
        def dfs(nums):
            if len(nums) < 2:
                return 1
            left = [x for x in nums if x < nums[0]]
            right = [x for x in nums if x > nums[0]]
            m, n = len(left), len(right)
            a, b = dfs(left), dfs(right)
            return (((c[m + n][m] * a) % mod) * b) % mod

        n = len(nums)
        mod = 10**9 + 7
        c = [[0] * n for _ in range(n)]
        c[0][0] = 1
        for i in range(1, n):
            c[i][0] = 1
            for j in range(1, i + 1):
                c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod
        return (dfs(nums) - 1 + mod) % mod

speed

复杂度分析

指标	值
时间	O(m^2)
空间	O(m^2)

psychology

面试官常问的追问

外企场景

question_mark
Candidate shows strong understanding of divide and conquer techniques in solving tree-based problems.
question_mark
Candidate demonstrates the ability to optimize recursive solutions using dynamic programming and memoization.
question_mark
Candidate is able to efficiently apply combinatorics to count valid reorderings within subarrays of the BST.

warning

常见陷阱

外企场景

error
Failing to account for all possible reorderings within each subtree.
error
Not properly using memoization, leading to redundant recalculations.
error
Incorrectly calculating binomial coefficients or failing to apply them in subtree reorderings.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handling larger tree structures with increased complexity in counting reorderings.
arrow_right_alt
Introducing additional constraints, such as restricting specific numbers to particular positions.
arrow_right_alt
Optimizing for space complexity, especially when dealing with very large arrays.

help

常见问题

外企场景

继续练习

#1467 两个盒子中球的颜色数相同的概率 #1728 猫和老鼠 II #1382 将二叉搜索树变平衡