Morris Traversal 主要解決的是 binary tree traversal 的問題，講到 binary tree traversal，一般人直覺就會想到可以做 preorder, inorder, postorder traversal 求解，但是上述方法一般的實作方式(recursive or iterative + stack) 其 空間複雜度皆為 O(n)，原因是我們必須要紀錄尚未走訪的 node，例如在 inorder traversal 中，我們先照著 左子樹-> root ->右子樹的順序遍歷，如果不用 stack 紀錄 root，當我們走訪完左子樹之後就無法回到 root 繼續走訪。那要怎摸在不使用 stack (額外空間) 的情況下完成 traversal 呢？ Morris Traversal 正是為此而生，它可以在 O(1) space 情況下同樣達到 O(n) 時間複雜度完成 traversal。
概念:
Morris Traversal 主要的概念就是利用 leaf node 的空指標來分別紀錄中序順序中的前一個 node 與後一個 node，每個有 n 個 nodes 的 binary tree 會有 n+1 條 null link，利用這些 null link 來做紀錄就可以不使用額外的空間。
Algorithm:
1. 如果當前節點的左子點為空，則輸出當前節點並將其右子點作為當前節點。
2. 如果當前節點的左子點不為空，則在它的左子樹中找到它在中序遍歷中的前驅節點(predecessor)
2a. 如果 predecessor 的右子點為空，則將當前節點作為它的右子點，並將當前節點的左子點作為當前節點。
2b, 如果 predecessor 的右子點不為空，說明已經走過這個路線兩次，表示當前節點的左子樹皆已完成遍歷，因此將 predecessor 的右子點設為 null，並輸出當前節點，最後將當前節點的右子點作為新的當前節點。
3. 重複 1, 2 直到當前節點為 null。
Pseudo code:
current = root;
while current != null {
if current->left == null {
visit(current);
current = current->right;
}
else {
// 左子樹的最右邊的leaf node 就是當前 node 的 predecessor
predecessor = findPredecessor(current);
if predecessor->right == null {
predecessor->right = current;
current = current->left;
}
// 表示當前 node 的左子樹已經整個都走訪過了
else {
predecessor->right = null;
visit(current);
current = current->right;
}
}
應用:
沒有留言:
張貼留言