[알고리즘] Tree Traversal - Depth First Traversal

Depth First Traversal로 진행되는 트리 순회는

- preorder(root-> left -> right) 

- inorder(left->root->right)

- postorder(left->right->root) 

가 존재한다.

 

www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/

Tree Traversals (Inorder, Preorder and Postorder) - GeeksforGeeks

 

Inorder Traversal(left->root->right)

알고리즘:

1. left subtree를 순회 (= call inorder left-subtree)

2. visit root

3. right subtree를 순회(= call inorder right-subtree)

 

inorder를 사용하는 경우:

BST에서 inorder traversal은 노드 값이 감소하지 않는 순서(non-decreasing order) 로 순회 가능하다.

BST에서 증가하지 않는 순서(non-increasing order)로 노드를 얻기 위해선 reversed inorder traversal이 필요

 

eazymean.tistory.com/56

[leetcode 94] Binary Tree Inorder Traversal

 

 

Preorder Traversal(root->left->right)

알고리즘:

1. visit the root

2. left subtree를 순회 (= call preorder left-subtree)

3. right subtree를 순회 (= call preorder right-subtree)

 

preorder를 사용하는 경우:

1. 트리를 copy할 때 사용된다.

2. expression tree에서 prefix expression을 얻을때 사용

 

leetcode.com/problems/flatten-binary-tree-to-linked-list/

Flatten Binary Tree to Linked List - LeetCode

 

 

Postorder Traversal(left->right->root) 

알고리즘:

1. left subtree를 순회 (= call preorder left-subtree)

2. right subtree를 순회 (= call preorder right-subtree)

3. visit the root

 

postorder를 사용하는 경우:

1. 트리를 삭제할 때 사용. 

2. expression tree에서 postfix expression을 얻을때 사용

 

 

 

 

 

이 때 트리를 순회하는 방법 세 가지

 

1.Recursive

- 가장 간단한 구현방법

- 예를 들어 inorder의 경우 가장 왼쪽 아래 있는 노드 부터: 왼쪽 -> 루트 -> 오른쪽 순서로 진행하기 때문에

root에서 출발

recursive(root->left)

result.add value(root)

recursive(root->right)가 된다.

- time complexity: O(N) 

- space complexity: O(N) 

 

2. Stack 이용

- 스택을 이용해서 pop할 때마다 정답에 저장한다.

- 말단 노드까지 전부 push한 다음 스택에 탑에서 부터 pop하여 따진다.

- inorder의 경우 root부터 가장 왼쪽 아래 노드까지 스택에 push

-> 스택의 탑을 pop: 이 때 pop한 값이 cur가 된다.(왼쪽 노드가 더이상 없기 때문)

-> cur의 값을 정답에 저장하고 cur->right로 옮겨 간다.

 

 

3. Morris Traversal

- inorder에서만 사용가능

- 현재 노드가 left가 존재하지 않는다면 현재노드의 값을 정답에 추가하고 right 노드로 이동한다.

- 현재 노드가 left가 존재한다면 

   - 현재 노드의 left subtree를 찾는다.

   - left subtree에서 right most node를 찾는다.

   - right most node에 현재노드 + 현재노드의 right subtree를 붙인다.

 

1. init cur node as root

2. while cur is not null

 1) if cur->left is null

     - result.push(cur.val)

     - cur = cur->right

 2) else

     - sub = cur->left ; left subtree로 이동

     - while(sub != null) sub = sub->right; right most node찾기

     - make the cur right child of sub

     - cur = cur->left

 

왼쪽 subtree의 가장 오른쪽 노드인 5에 주목한다.

 

 

 

 

5의 right child로 루트노드를 붙인다.

 

 

 

 

 

 

 

 

 

결론적으로 이런 모양