1569. Number of Ways to Reorder Array to Get Same BST

LeetCode 原题

Given an array nums that represents a permutation of integers from 1 to n. We are going to construct a binary search tree (BST) by inserting the elements of nums in order into an initially empty BST. Find the number of different ways to reorder nums so that the constructed BST is identical to that formed from the original array nums.

• For example, given nums = [2,1,3], we will have 2 as the root, 1 as a left child, and 3 as a right child. The array [2,3,1] also yields the same BST but [3,2,1] yields a different BST.

Return the number of ways to reorder nums such that the BST formed is identical to the original BST formed from nums.

Since the answer may be very large, return it modulo 109 + 7.

思路:DFS

根节点是固定的，因此构成左树的节点和构成右树的节点是确定的。

假设我们已知左树和右树可能的个数，现在无非想要知道，对于每种可能的树的形状的组合，有几种构造顺序。显然单个树的内部构造顺序不能变（否则根节点数字变了，树的构造也变了），因此能改变的只有左树与右树元素添加的相对顺序。我们可以对所有元素进行全排列，然后分别去除左树与右树内部的顺序（因为只有一种排列是合法的）。因此，最后的结果就是：左树个数右树个数C(总节点数，左树节点数)

Base case就是不足以分出左，根，右的情况。此时有且只有一种排列方式

写成代码就是如下的：

class Solution:
    def numOfWays(self, nums: List[int]) -> int:
        mod = 10 ** 9 + 7
        
        def dfs(nums):
            m = len(nums)
            if m < 3: 
                return 1
            left_nodes = [a for a in nums if a < nums[0]]
            right_nodes = [a for a in nums if a > nums[0]]
            return dfs(left_nodes) * dfs(right_nodes) * comb(m - 1, len(left_nodes)) % mod
        
        return (dfs(nums) - 1) % mod