LeetCode 解題紀錄 449. Serialize and Deserialize BST

Serialize and Deserialize BST - LeetCode

題目

完成一個能將 BST 轉換成字串的函數，以及能將字串還原成 BST 的函數

限制

• 0 ≤ BST 節點數 ≤ 10⁴
• 0 ≤ BST 節點值 ≤ 10⁴

觀察

• 可以將值轉換成字串再以特定分隔號連結，分辨之後用 spilt() 函數
• BST 的左子節點必定小於節點，右子節點必定大於節點
• 重建 BST 時必須從根節點開始，因此轉換字串時，跟節點必須是第一個

思路

• 使用 preorder 訪問法進行 DFS，好讓根節點成為第一個字串
• 還原時利用建立 BST 的方法，用比較節點值來決定新增子節點的位置
• 建立字串與還原的順序一樣，建立出來的 BST 也會一樣

Trial 1

結果

建立字串的時間/空間複雜度為 O(n)，還原 BST 的時間複雜度為 O(nLogn)因為每次都從根節點開始搜尋

Trial 2

• 如果這只是 BT 的話，不包含順序特性時，可以使用特定字元來表示空節點，這樣就能知道什麼時候該建立左/右子節點或已經到達葉節點

結果

還原的時間複雜度降為 O(n)