1569. Number of Ways to Reorder Array to Get Same BST¶
题目信息¶
- 题号:
1569
- 难度:
Hard
- 主题:
二叉搜索树、组合数学、递归
- 原题:
- 重点:
按数组顺序向空二叉搜索树插入互不相同元素;统计得到相同树结构的重排数量,并排除原排列
题目重述¶
给定由互不相同正整数组成的数组 nums。按数组顺序把元素依次插入一棵初始为空的二叉搜索树。
请统计对 nums 重新排列后,仍能构造出与原排列完全相同二叉搜索树的排列数量,不包含原排列本身。答案对 10^9 + 7 取模。
1 <= nums.length <= 1000,元素互不相同。
自建示例¶
左右子树元素的相对插入顺序可以交错:
输入:nums = [2,1,3]
输出:1
解释:排列 [2,3,1] 得到同一棵树;排除原排列后只剩这一种。
严格递增数组只有原排列能形成同一条右链:
输入:nums = [1,2,3]
输出:0
解释:改变插入顺序会改变根节点或树结构。