LeetCode 解題紀錄 2196. Create Binary Tree From Descriptions

Create Binary Tree From Descriptions - LeetCode

題目

給定一個二維陣列，每個元素包含三個資料，父節點的值，子節點的值，子節點是左或是右，根據這個的陣列建立二元樹回傳這個二元樹的跟節點

限制

• 陣列長度 1~ 104
• 節點的值介於 1~105，節點的值為唯一

觀察

• 節點值為唯一，可視為該節點的 id
• 把陣列看成有向圖的路徑關係，轉化成 adjacent list
• 轉化過程中同時計算每個節點的 in degree，in degree 為 0 的節點就是根節點
• 利用 DFS 從根節點建立整個 tree

Trial 1

• binary tree 與有向圖的一點區別是，子節點有分左右，為了解決這個問題，我使用負數的 key 來區分，因為題目中節點的值皆為正數

結果

時間/空間複雜度都是 O(n)

Trial 2

參考了別人的作法，流程更加精簡，使用 Map 在訪查陣列的同時就已經開始在建立 binary tree的節點並加以連接，這個方法讓程式碼可讀性更高

結果

時間與空間複雜度不變，執行時間與記憶體使用也很接近