[C++] LeetCode : Binary Tree Inorder Traversal

Question

주어진 Binary Tree를 inorder (중위 순회) 방식으로 탐색하는 문제이다. 자료구조의 Binary Tree의 탐색 부분을 공부할 때 접하게 되는 기본적인 순회 방법 중 하나로 , 재귀적인 방법을 사용하면 간단하게 풀 수 있다. 하지만 문제에서는 iterative방식으로 해결해 볼 것 을 권장하고 있다.

제약사항

• 노드의 개수는 최소 0개 최대 100개이다
• 각 노드의 값은 최소 -100 ~ 최대 100이다
  
  

---

Solution

• 가능한 최선의 수행 시간(Best Conceivable Runtime(BCR))
  트리 노드의 개수를 n이라 했을 때 적어도 한번씩은 다 방문해야 하므로 시간 복잡도는 O(n)이다
  
  
• 고려사항
  빈 노드가 주어질 때

• Solution1 (Recursive)
  가장 기본적인 순회 방법이다, 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 순으로 방문한다. 

/*
 * 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:
    void traverse(TreeNode* root, vector<int>& ans) {
        if (root == NULL) return;

        traverse(root->left, ans);
        ans.push_back(root->val);
        traverse(root->right, ans);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        traverse(root, ans);
        return ans;
    }
};

• Time complexity : O(n) // O(n) = 2* O(n/2) + 1
• Space Complexity : O(n) // 추가 공간은 보통 트리의 높이에 비례하기 때문에 O(logn)이지만, 최악의 경우 Tree가 한쪽으로 쏠려있을 때 O(n)이다

• Solution2 (Iterative Method 1)
  스택을 이용한 방법이다.  왼쪽 자식 노드를 계속 쌓아준 뒤, 부모 노드의 값을 넣고 오른쪽 자식 노드 기준으로 다시 왼쪽 자식 노드를 쌓아주는 방식이다.

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> node_val_vec;
        stack<TreeNode*> node_stack;
        
        TreeNode* curr = root;
        while(curr != NULL || !node_stack.empty()){
            while(curr != NULL){
                node_stack.push(curr);
                curr = curr->left;
            }
            
            curr = node_stack.top();
            node_stack.pop();
            node_val_vec.push_back(curr->val);
            curr = curr->right;
        }
        
        return node_val_vec;
    }
};

• Time complexity : O(n) 
• Space Complexity : O(n)
  

• Solution3 (Iterative Method 2)
  Morris Traversal를 이용한 방법이다. 현재까지의 모든 방법들은 트리의 형태를 변형하지 않았다면, Morris 알고리즘은 트리의 형태를 변형하는 방법이다. 일반적인 Inorder Traverse는 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 순으로 탐색한다. 만약 왼쪽 자식 노드가 없는 트리라면, 즉, 부모 노드-> 오른쪽 자식 노드 로만 이루어진 트리라면 트리는 Linked List와 다를 게 없다. Morris 알고리즘은 트리를 위와 같은 형태로 변형시켜 순회하는 방법이다. 방법은 아래와 같다.

Step 1: current를 root노드로 초기화 한다.
Step 2: current 노드가 NULL 일때 까지 아래 과정을 반복한다. 

만약 current 노드의 왼쪽 자식 노드가 없다면
  a. current val 값을 return 할 vector에 추가한다.
  b. current의 오른쪽 자식 노드로 이동한다. // current = current -> right;

그게 아니라면 
  a. current의 왼쪽 서브 트리의 오른쪽 자식 끝 노드에 current를 연결 한다.
  b. current의 왼쪽 자식 노드로 이동한다. // current = current -> left;

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> node_val_vec;
        
        TreeNode* curr = root;
        while(curr != NULL){
            if(curr->left == NULL){
                node_val_vec.push_back(curr->val);
                curr = curr->right;
            }else{
                TreeNode* copy = curr->left;
                while(copy->right != NULL) copy = copy->right;
                copy->right = curr;
                TreeNode* temp = curr;
                curr = curr->left;
                temp->left = NULL;
            }
        }
        return node_val_vec;
    }
};

• Time complexity : O(n) 
• Space Complexity :  O(1) // 추가 공간을 사용하지 않기 때문에 O(1)이다.

 

출처 : https://leetcode.com/problems/binary-tree-inorder-traversal/

Binary Tree Inorder Traversal - LeetCode

* 본 포스트 관련된 토의, 지적 및 조언은 모두 환영합니다