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

题目信息

题号:

1569

难度:

Hard

主题:

二叉搜索树、组合数学、递归

原题:

LeetCode 1569

重点:

按数组顺序向空二叉搜索树插入互不相同元素;统计得到相同树结构的重排数量,并排除原排列

题目重述

给定由互不相同正整数组成的数组 nums。按数组顺序把元素依次插入一棵初始为空的二叉搜索树。

请统计对 nums 重新排列后,仍能构造出与原排列完全相同二叉搜索树的排列数量,不包含原排列本身。答案对 10^9 + 7 取模。

1 <= nums.length <= 1000,元素互不相同。

自建示例

左右子树元素的相对插入顺序可以交错:

输入:nums = [2,1,3]
输出:1
解释:排列 [2,3,1] 得到同一棵树;排除原排列后只剩这一种。

严格递增数组只有原排列能形成同一条右链:

输入:nums = [1,2,3]
输出:0
解释:改变插入顺序会改变根节点或树结构。