今天來複習一下常見遍歷樹的方式。
Recursive way
Inorder traversal
先拜訪 left subtree,再依序拜訪 root node 跟 right subtree。
1
2
3
4
5
6
7
8
9
10
| void Inorder_traversal(TreeNode *node){
if (node == NULL){
return;
}
Inorder_traversal(node->left);
cout << node->val << " ";
Inorder_traversal(node->rihgt);
return;
}
|
Preorder traversal
先拜訪 root node,再依序拜訪 left subtree 跟 right subtree。
1
2
3
4
5
6
7
8
9
10
| void Preorder_traversal(TreeNode *node){
if (node == NULL){
return;
}
cout << node->val << " ";
Preorder_traversal(node->left);
Preorder_traversal(node->rihgt);
return;
}
|
Postorder traversal
先依序拜訪 left subtree 跟 right subtree,再拜訪 root node。
1
2
3
4
5
6
7
8
9
10
| void Postorder_traversal(TreeNode *node){
if (node == NULL){
return;
}
Postorder_traversal(node->left);
Postorder_traversal(node->rihgt);
cout << node->val << " ";
return;
}
|
可以看到用 recursive 寫的話,三種方式的 code 基本上長一樣,而且複雜度也都一樣,只是差在遍歷 root node 的時間不一樣。
time complexity: $O(n)$
space complextiy: $O(h)$, where $h = $ tree height
Iterative way
但是我覺得比較有趣的是 iterative 的方式,三種方式各有要注意的地方。
Inorder traversal
- 不斷往左邊走,走的過程中把 current push 到 stack 裡面,直到 current 變成 NULL
- current = stack.top()
- 往右邊走
- 重複步驟 1
由於 Inorder traversal 的順序是 left subtree -> root node -> right subtree,因此步驟 1 要不斷往左邊走。
當 current == NULL
的時候,代表沒有 left subtree 了,此時 stack.top()
就會是剛剛的 root node,因此讓 current = stack.top()
,並且印出來。
接下來往右邊走,等同於遍歷 right subtree,最後重複步驟 1 直到整個過程結束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void Inorder_traversal(TreeNode *node){
stack<TreeNode*> stk;
TreeNode *cur = node;
while (not stk.empty() || cur != NULL){
while (cur != NULL){
stk.push(cur);
cur = cur->left;
}
cur = stk.top();
stk.pop();
cout << cur->val << " ";
cur = cur->right;
}
return;
}
|
Preorder traversal
這邊的 code 基本上跟 Inorder traversal 長一樣,唯一的差別就是印出來的時機。
由於 Preorder traversal 的順序是 root node -> left subtree -> right subtree,因此在走到 left subtree 之前,就要先印出來。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void Preorder_traversal(TreeNode *node){
stack<TreeNode*> stk;
TreeNode *cur = node;
while (not stk.empty() || cur != NULL){
while (cur != NULL){
cout << cur->val << " ";
stk.push(cur);
cur = cur->left;
}
cur = stk.top();
stk.pop();
cur = cur->right;
}
return;
}
|
不過我還有看到另外一個方法,思路不太一樣。
這個的想法比較簡單,不斷 push 右邊跟左邊的節點,就可以保證左邊的節點一直在 stack 的上面,進而實現 Preorder traversal。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void Preorder_traversal(TreeNode *node){
stack<TreeNode*> stk;
stk.push(node);
while (not stk.empty()){
cur = stk.top();
stk.pop();
cout << cur->val << " ";
if (cur->right != NULL){
stk.push(cur->right)
}
if (cur->left != NULL){
stk.push(cur->left)
}
}
return;
}
|
不過可以發現 cur->left
在 push 進去之後,立刻就被 pop 出來,因此實際上可以不需要 push 進去。
下面這段 code 跟 Preorder 的第一段長得很像,但是想法不太一樣。
第一段是往左邊走的時候 push current,並且 pop 的時候再往右邊走。
這邊是往左邊走的時候 push right child,pop 的時候就是右邊的節點,基本上是一樣的方法。
要特別注意的是,這邊需要檢查 stack 是否為空的,原因是如果 cur->right == NULL
,此時並不會 push 任何東西到 stack 裡面。可以用 2 為 root,1 為 left child 的 binary tree 想想看,如果此時沒有檢查 stack 是否為空,會出現錯誤。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void Preorder_traversal(TreeNode *node){
stack<TreeNode*> stk;
TreeNode *cur = node;
while (not stk.empty() || cur != NULL){
while (cur != NULL){
cout << cur->val << " ";
if (cur->right != NULL){
stk.push(cur->right);
}
cur = cur->left;
}
if (not stk.empty()){
cur = stk.top();
stk.pop();
}
}
return;
}
|
Postorder traversal
Postorder traversal 的順序是 left subtree -> right subtree -> root node,其實可以反過來做,也就是 root node -> right subtree -> left subtree 然後再反轉結果就好(如果是把順序存到 vector 裡面的話)。
root node -> right subtree -> left subtree 就是剛剛做過的 Preorder traversal,只是 left subtre、right subtree 反過來而已。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| vector<int> Postorder_traversal(TreeNode *node){
vector<int> result;
stack<TreeNode*> stk;
TreeNode *cur = node;
while (not stk.empty() || cur != NULL){
while (cur != NULL){
result.push_back(cur->val);
stk.push(cur);
cur = cur->right;
}
cur = stk.top();
stk.pop();
cur = cur->left;
}
reverse(begin(result), end(result));
return result;
}
|
不過這樣不太有效率,因為需要額外的空間來儲存印出來的順序。
Postorder traversal 難的地方在於在遍歷 right subtree 之後,還要回到 root。
在前面的 Preorder 跟 Inorder traversal 中,當把 root pop 出來之後,接下來往右走就好,因為接下來都不會再用到 root node。
但是 Postorder traversal 中,往右走之後,還要想辦法回到 root。
有一個聰明的方法就是 push 兩次 root node。
如果是第一次 pop root node(也就是現在要拜訪 right subtree),那麼此時 cur == stk.top()
,選擇往右走。
如果是第二次 pop root node(也就是現在要拜訪 root node),那麼此時只要印出來就好。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void Postorder_traversal(TreeNode *node){
stack<TreeNode*> stk;
TreeNode *cur = node;
while (not stk.empty() || cur != NULL){
while (cur != NULL){
stk.push(cur);
stk.push(cur);
cur = cur->left;
}
cur = stk.top();
stk.pop();
if (not stk.empty() && cur == stk.top()){
cur = cur->right;
}
else {
cout << cur->val << " ";
cur = NULL;
}
}
return;
}
|
參考資料
- https://shubo.io/iterative-binary-tree-traversal/
- https://www.geeksforgeeks.org/iterative-preorder-traversal/
- https://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/