HardRating 2288

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

arraymathdivide-and-conquerdynamic-programmingtreeunion-findbinary-search-treememoizationcombinatoricsbinary-tree

解題說明

Number of Ways to Reorder Array to Get Same BST

題目描述：給定一個由 1 到 n 的排列組成的陣列 nums，代表一棵 BST 的插入順序。求有多少種不同的排列方式可以得到相同結構的 BST。答案對 10^9 + 7 取餘。

解題思路：根節點（第一個元素）固定不變。小於根的元素構成左子樹，大於根的元素構成右子樹。左右子樹內的相對順序決定了子樹結構，但左右子樹的元素可以交錯排列。交錯方式的數量為 C(left+right, left)。遞迴地對左右子樹計算方案數，然後乘以交錯數。使用 Pascal 三角形預計算組合數。

C++ 解法

複雜度分析

時間複雜度：O(n^2) — 每個節點被遍歷一次來分組，Pascal 三角形預計算 O(n^2)

空間複雜度：O(n^2) — Pascal 三角形儲存 + 遞迴中的子陣列

虛擬碼

1. Precompute Pascal's triangle C[n][k] modulo 10^9+7
2. DFS function on array:
   a. Base case: if array size <= 2, return 1
   b. Root = first element
   c. Split remaining into left (< root) and right (> root)
   d. Recursively compute left ways and right ways
   e. Return C[left.size + right.size][left.size] * leftWays * rightWays
3. Return dfs(nums) - 1 (exclude original ordering)

其他解法

方法二：Lucas 定理 + 快速冪求組合數 如果 n 非常大，可以用 Lucas 定理和模逆元來計算組合數，避免 O(n^2) 的預計算。適合 n 超過 10^5 的情況。

方法三：記憶化搜尋 將子陣列的結構特徵（如最小值、最大值、大小）作為 key 進行記憶化。但由於子陣列內容不同，實際上難以找到有效的 key，不如直接遞迴。

延伸思考

如果要輸出所有等價排列（而非只計數），你會使用什麼方法？
如果插入順序可以相同（存在重複元素），計數方式需要如何修改？
這道題和求二元樹的拓撲排序數量有什麼關係？

Number of Ways to Reorder Array to Get Same BST — CaffeCode