Shulou(Shulou.com)06/01 Report--

This article is about how leetcode finds the number of solutions for reordering subarrays to the same binary search tree. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

Give you an array of nums to represent an arrangement of 1 to n. We insert a binary search tree (BST) that is initially empty in the order in which the elements are in the nums. Please count the number of solutions that meet the following conditions after reordering nums: the binary search tree obtained after rearrangement is the same as the binary search tree obtained by nums in the original numerical order.

For example, if I give you nums = [2jue 1jue 3], we get a tree with two roots, one for the left child and three for the right child. The same BST can be obtained from the array, but a different BST can be obtained from the array.

Please return to rearrange nums and get the same number of binary search trees as the original array nums.

As the answer may be large, please take the remainder of the result to 10 ^ 9 + 7.

Example 1:

Input: nums = [2, 1, 1, 3]

Output: 1

Explanation: we rearrange the nums so that we can get the same BST. There is no other solution to get the same BST.

Example 2:

Input: nums = [3, 4, 5, 5, 1, 2]

Output: 5

Explanation: the following five arrays will get 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, 2, 3]

Output: 0

Explanation: no other order can get the same BST.

Example 4:

Input: nums = [3, 1, 2, 5, 4, 6]

Output: 19

Example 5:

Input: nums = [9, 4, 2, 1, 3, 6, 5, 7, 8, 14, 11, 10, 12, 13, 16, 15, 17, 18]

Output: 216212978

Explanation: the number of scenarios that get the same BST is 3216212999. After taking the remainder of 10 ^ 9 + 7, you get 216212978.

Tip:

one

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.