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)

大師