#1569
Number of Ways to Reorder Array to Get Same BST
candidate master · 1330 · lc hard +32 · verified · 54% accepted · 1,853 likes · top 46%
Description
Given an array nums which is a permutation of integers from 1 to n, inserting the elements one by one into an empty BST produces a specific tree. Count the number of distinct reorderings of nums that produce the same BST structure. Return the count modulo 109 + 7.
Example 1:
Input: nums = [2,1,3]
Output: 1
Explanation: We can reorder nums to be [2,3,1] which will yield the same BST. There are no other ways to reorder nums which will yield the same BST.
Example 2:
Input: nums = [3,4,5,1,2]
Output: 5
Explanation: The following 5 arrays will yield the same 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]
Example 3:
Input: nums = [1,2,3]
Output: 0
Explanation: There are no other orderings of nums that will yield the same BST.
Code
1
2
3