[Tree] Tree Traversal (Pre-, In-, Post-Order)

Node가 언제 탐색되느냐를 기준으로

• Pre- (맨 먼저)
• In- (Left child -> root -> right child 순으로)
• Post- (children 탐색 후 맨 마지막)

로 구분한다.

 

트리는 재귀적인 구조를 가지므로, 재귀함수를 이용하면 쉽게 Traversal 구현이 가능하다.

Base case로, 인자가 null일때 출력 안하고 return 하도록 하고,

Left/right children에 대한 재귀 호출과 현재 root node 값 출력 순서를 어떻게 정의하느냐에 따라 종류가 달라짐.

 

아래는 재귀로 푼, Binary Tree traversal Leetcode 문제

leetcode.com/problems/binary-tree-inorder-traversal/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v = vector<int>();
        if(!root) return v;
                
        vector<int> v1 = inorderTraversal(root->left);
        vector<int> v2 = inorderTraversal(root->right);
        v.insert(v.end(), v1.begin(), v1.end());
        v.push_back(root->val);
        v.insert(v.end(), v2.begin(), v2.end());
        return v;
    }
};

* Pre, Post order는, v.push_back(root->val); 위치만 바꿔주면 됨.

 

---

사실 재귀로 푸는건 누구나 할 수 있다.

재귀는 반드시 iterative한 방법으로도 구현할 수 있는데, traversal도 다시 구현해보자.

 

In-order를 구현한다고 치자.

Left child traversal이 끝나야 root 노드 값을 출력하고 right child traversal을 탐색해야 한다.

그런데, left child traversal 할 때, 기존 root 노드 값이나 right child를 traversal 해야 한다는 정보를 어떻게 저장할 수 있을까?

 

우리가 재귀함수를 호출하면, 재귀함수를 호출한 caller의 정보는 stack memory에 저장된다.

재귀함수가 일을 마치고 return할때는 stack memory에 저장됬던 caller의 정보를 pop해서, 다시 재귀 호출 전 프로그램의 상태를 복구시킨다.

여기서 배울 점 : 우리는 스택을 사용해서 left child traversal 이전의 정보를 저장하고 복구할 수 있다! 

 

스택에 노드를 넣을 땐, 먼저 방문해야 하는 노드를 맨 마지막에 넣어야 한다.

 

Pre-order
leetcode.com/problems/binary-tree-preorder-traversal/

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> v {};
        stack<TreeNode*> s;

        s.push(root);
        while(!s.empty()){
            auto now = s.top(); s.pop();
            if(now == nullptr) continue;

            v.push_back(now->val); // 현재 root 값 기록
            s.push(now->right); // right 나중에 방문
            s.push(now->left); // left 먼저 방문
        }
        return v;
    }
};

 

In과 Post order 구현시에는 약간의 문제점이 있다.

root의 값을 children 탐색 이후에 출력해야하는데, stack에서 root노드를 뽑았을 때

이 노드가 이미 children을 처리해서 값만 출력하면 되는 노드인지, 아니면 children 탐색을 아직 안한 새로운 root노드인지 (이 경우 children부터 탐색해야함) 알 길이 없다.

 

그래서, stack에 넣을때 boolean으로 visited 여부를 같이 넣어준다.

root 노드에서 children을 처리하고 다시 값 출력을 위해 스스로를 스택에 넣을 때, visited = true값을 같이 넣어주는 것이다.

 

In- / Post-order
leetcode.com/problems/binary-tree-postorder-traversal/

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v {};
        stack<pair<TreeNode*, bool>> s;

        s.push({root, false});
        while(!s.empty()){
            auto [now, visited] = s.top(); s.pop();
            if(now == nullptr) continue;
            if(visited) {
                v.push_back(now->val);
                continue;
            }
            
            s.push({now->right, false});
            s.push({now, true}); // left 먼저 탐색 후, 현재 root 값 기록
            s.push({now->left, false});
        }
        return v;
    }
};

//-------------------------------------------------------------------
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> v {};
        stack<pair<TreeNode*, bool>> s;

        s.push({root, false});
        while(!s.empty()){
            auto [now, visited] = s.top(); s.pop();
            if(now == nullptr) continue;
            if(visited) {
                v.push_back(now->val);
                continue;
            }
            
            s.push({now, true}); // children 모두 탐색 후, 현재 root 값 기록
            s.push({now->right, false});
            s.push({now->left, false});
        }
        return v;
    }
};

 

위 문제들은 Binary-Tree의 경우였지만,

사실 N-ary Tree traversal도 원리는 같다.
(재귀호출 시, 혹은 스택에 넣어줄 때 child를 여러 개 처리해줘야 한다는 차이점만 있을 뿐)

leetcode.com/problems/n-ary-tree-preorder-traversal/

N-ary Tree Preorder Traversal - LeetCode

 

---

21May21)

LeetCode에서 'Maximum Depth of Binary Tree' 문제 풀고 다시보니까, 그냥 DFS를 stack으로 구현한 거랑 비슷하네

Tree search (DFS)나, Tree traversal (In-/Pre-/Post-Order)이나, 트리 전체 돌아야 할 때는 같네(보통 DFS를 Pre-order 방식으로 구현하는 듯)

 

https://leetcode.com/explore/featured/card/top-interview-questions-easy/94/trees/555/

Explore - LeetCode

 

---

24Aug21) In-order traversal의 경우, stack을 이용한 다른 구현 방법 존재.

Left branch를 모조리 stack에 넣는 pushAllLeft 함수 구현 후, pop할때마다 right child에 pushAllLeft 호출

→ left - root - right 순서(in-order)로 출력

 

https://leetcode.com/problems/binary-search-tree-iterator/discuss/52525/My-solutions-in-3-languages-with-Stack

My solutions in 3 languages with Stack - LeetCode Discuss