1569. Number of Ways to Reorder Array to Get Same BST
用 array nums 建构 BST 的方法可以是将 nums 中的元素依序插入 BST 中
一开始 BST 没有东西所以 root 会是 nums[0]
给你一个 array，问你有几种和他不同的 array 能建出和他一样的 BST
Example 1:
https://assets.leetcode.com/uploads/2020/08/12/bb.png
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:
https://assets.leetcode.com/uploads/2020/08/12/ex1.png
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]
思路:
1.从 BST 的长相倒推会比较好想
以 Example 2 为例 nums[0] 一定要是 3 因为 BST 的 root 就是 3
接下来左右子树的插入都不会互相干扰
而左子树中 1 一定要比 2 先插入
右子树中 4 一定要比 5 先插入
有点在算排列的感觉 这种状况下的排列数=4!/2!/2!
也就是全部元素排列 -> 整理 (1,2) 和 (2,1) -> 整理 (4,5) 和 (5,4)
2.如果写笼统一点呢 假如知道一个 node
左子树有 L1 个元素 有 L2 个不同的合法排列
右子树有 R1 个元素 有 R2 个不同的合法排列
那全部元素排列 = (L1+R1)! 这里记得 node 必须摆在第一位 所以不用+1
然后整理左子树的元素成合法结果 -> (L1+R1)! / L1! * L2
整理右子树的元素成合法结果 -> (L1+R1)! / L1! * L2 / R1! * R2
移项一下可以变成 C(L1+R1, L1) * L2 * R2
也就是这个 node 子树的合法排列数 元素数量则是 L1+R1+1
3.建完 BST 后就能 DFS 算完
Python code:
class Solution:
def numOfWays(self, nums: List[int]) -> int:
class Node:
def __init__(self, v):
self.val = v
self.left = None
self.right = None
def insert(self, node):
if node.val > self.val:
if not self.right:
self.right = node
else:
self.right.insert(node)
else:
if not self.left:
self.left = node
else:
self.left.insert(node)
def cal(node):
if not node:
return (0, 1)
lnum, lway = cal(node.left)
rnum, rway = cal(node.right)
res = lway * rway * comb(lnum+rnum, lnum) % (10**9+7)
return (lnum+rnum+1, res)
root = Node(nums[0])
for num in nums[1:]:
root.insert(Node(num))
return (cal(root)[1]-1) % (10**9+7)
竟然比 O(n^2) 直接算不建 BST 还慢
这是为什么呢......

点太少吗 树要多做事

应该是 bst 最差也是O(n^2)

大师