MediumRating 1260

1305. All Elements in Two Binary Search Trees

treedepth-first-searchbinary-search-treesortingbinary-tree

解題說明

All Elements in Two Binary Search Trees

題目描述：給定兩棵二元搜尋樹 root1 和 root2，回傳一個包含兩棵樹中所有元素的排序串列。

解題思路：對兩棵 BST 分別進行中序遍歷（inorder traversal），可以得到兩個已排序的陣列。然後使用合併排序中的合併步驟（merge），將兩個已排序陣列合併為一個排序串列。這利用了 BST 中序遍歷產生升序序列的性質。

C++ 解法

複雜度分析

時間複雜度：O(m + n) — 其中 m 和 n 分別是兩棵樹的節點數，中序遍歷各需 O(m) 和 O(n)，合併需 O(m + n)

空間複雜度：O(m + n) — 儲存兩個中序遍歷結果和最終合併結果

虛擬碼

1. Perform inorder traversal on root1 to get sorted list1
2. Perform inorder traversal on root2 to get sorted list2
3. Merge list1 and list2 using two pointers:
   a. While both lists have elements, pick the smaller one
   b. Append remaining elements from whichever list is non-empty
4. Return merged result

其他解法

方法二：迭代中序遍歷 + 即時合併 使用兩個堆疊分別模擬兩棵 BST 的中序遍歷，每次從兩個堆疊頂部取較小值。這樣不需要先完整遍歷再合併，空間複雜度降為 O(h1 + h2 + m + n)，其中 h1、h2 為樹高（輸出陣列仍需 O(m+n)）。

方法三：扁平化後排序 將兩棵樹的所有節點放入同一個陣列，再排序。時間複雜度 O((m+n) log(m+n))，沒有利用 BST 的排序性質，效率較差。

延伸思考

如果兩棵樹非常不平衡（例如一棵有 100 萬節點，另一棵只有 10 個節點），有沒有更高效的方法？
如果要求只回傳第 k 小的元素而非全部，如何優化？
如果輸入不是 BST 而是一般的二元樹，解法需要如何改變？

All Elements in Two Binary Search Trees — CaffeCode