一、Tree & Binary tree & Binary search tree
1.1 基本觀念介紹
1.1.1 Tree
是一種模擬現實生活中樹幹和樹枝的資料結構，分為 :Root (根節點)：沒有父節點的節點，所以每棵樹只有一個 root，如 A；在根節點之下是樹的樹枝，擁有 0 到 n 個子節點。
Node (節點)：一個個連結點，如 A、B、C ... M 都是結點。
Parent (父節點) : 節點 B 是 I 和 J 的父節點。
Child (子節點) : 節點 I 和 J 是 B 的子節點。
Siblings (兄弟節點) : 擁有共同父節點，如 I 和 J、K 和 L 和 M。
Leaf (葉節點)：節點沒有子節點的節點稱為葉節點，如 I、J、K、L、M、F、G、H。
Ancenstors (祖先節點) : 指某節點到根節點之間所經過的所有節點，都是此節點的祖先節點。
Level (階層) : 如果樹根是階層 1，其子節點即是階層 2，依序可以計算出樹的階層數；如節點A 階層是1，B、C 到 H 是階層 2，I、 J 到 M 是階層 3。
Height (樹高) : 又稱為 Depth (樹深)，指樹的最大階層數，如此圖的樹高是 3。
Dregree (分支度)：指每個節點擁有的子節點數，如節點 B 的分支度是 2，節點 E 的分支度是 3。
--
最廣義的樹對於 node 之 child 數目沒有限制，因此每個 node 可以有多個 child。
Linked list 也可以視作是樹只是每個 node 都只有一個 child。
1.1.2 Binary tree
Left subtree (左子樹) : 節點左邊稱為左子樹。
Right subtree (右子樹) : 節點右邊稱為右子樹。
二元樹節點鏈結表示法 : 資料 + 結構指標(左) + 結構指標(右)。
1.1.3 Binary search tree
- 右側 node 的值一定會比左側大
- 節點的左、右子樹也是一棵二元搜尋樹
- 不可以有值重複的 node 值，在整棵二元樹中的每一個 node 都擁有不同值
- 可以推論出左側樹狀結構最尾端為 Binary search tree 的最小值，右側樹狀結構最尾端為 Binary search tree 的最大值
1.2 Traversal (走訪)
Array 和 singly linked list (單向鏈結串列) 都只能從頭至尾或從尾至頭執行單向 traverse，不過二元樹的每一個節點都擁有指向左和右 2 個子節點的指標，所以走訪可以有兩條路徑。 理論上總共有四種，但是事實上只有 DFS - Depth-first Search (深度優先搜尋) 與 BFS - Breath-first Search (廣度優先搜尋) 兩種，只不過更動了節點的輸出順序。
Preorder Traversal (前序遍歷) 遍歷順序是：根、左子樹、右子樹，根排在前面，即是 DFS；1245367
Inorder Traversal (中序遍歷) 遍歷順序是：左子樹、根、右子樹，根排在中間，即是 DFS；4251637
Postorder Traversal (後序遍歷) 遍歷順序是：左子樹、右子樹、根，根排在後面，即是 DFS；4526731
Level-order Traversal (層序遍歷) 遍歷順序是 : 由根節點層層往下，由左至右，即是 BFS；1234567
Preorder Traversal
Time complexity 是 O(n)，Space complexity 是 O(n)。
Inorder Traversal
Time complexity 是 O(n)，Space complexity 是 O(n)。
Postorder Traversal
Time complexity 是 O(n)，Space complexity 是 O(n)。
Level-order Traversal
Time complexity 是 O(n)，Space complexity 是 O(n)。
通常 BFS 都是用 queue 去實作，則只需要按照順序 1 → 2 → 3 → 4 → 5 → 6 → 7
1.3 實際運用範例
只要是大問題可以拆解成小問題的狀況都可以用到 tree traversal。
二、題目整理
Tree & Binary tree & Binary search tree 常出現之 LeetCode 題目整理
DFS (Depth-first search) 常出現之 LeetCode 題目整理
BFS (Breadth-first search) 常出現之 LeetCode 題目整理
- 題號 : 根據 LeetCode 題目出現的頻率, top interview 150 等整理的，但注意不代表這就涵蓋所有面試會考的題目。或你可以選擇 Grind 來安排你要刷的題目
- 難度 : 按照你現在想要的難度選擇刷題
- 重要性 : 比如說你注意到、或別人提到 Google 很常考這個題目之類，可以設定你覺得相對的重要性，之後可以拿來篩選用
- 第一次是否解出來 : 紀錄解題是否第一次就成功，若不成功可能需要複習
- 解題思路 : 題目的思路過程，寫大綱就好不用寫很詳細
- 其他解法 : 若解出來是否還可以想到其他解法，或是看到別人提供了更好的解法便記錄下來，在面試時還可以提出自己有不同解法
- 學到技巧 : 如此題可以用 two pointer 來解，寫下來下次遇到別的題目就可以知道說我多一個解法可以想想看可不可行
- 複習次數 : 用來記錄第一次解不出來的題目之練習次數
- 複習筆記 : 有可能再做一次還是解不出來，那可寫下這次癥結點是什麼，怎麼解決的，盡量完全理解解法，讓自己如果再做一次題目時若還是卡住，可以看筆記或是回想筆記試圖解出來
- 上次解題時間 : 可用來篩選下次該複習的題目
沒有留言:
張貼留言