전위순회, 중위순회, 후위순회

지난 시간에는 queue를 이용해서 bfs와 비슷한 level order traversal를 학습해보았는데, 이번 시간에는 재귀를 활용해서 dfs와 비슷한 전위순회(preorder traversal), 중위순회(inorder traversal), 그리고 후위순회(postorder traversal)을 학습해 보겠습니다.
💡순회 앞에 order가 어디 붙어있느냐에 따라 root 노드를 방문하는 순서가 달라집니다.

그 전에, 순회와 방문의 용어를 정확하게 알아봅시다.
🔖순회: 여러 곳을 돌아다니다
🔖방문: 노드의 값에 접근하는 것(출력, 저장 등)을 의미

즉, level order traversal로 보면, queue에서 poll하는 행위가 순회고, visited 배열에 현재 노드의 값을 저장하는 행위를 방문이라고 보면 됩니다.

위의 트리를 전위, 중위, 그리고 후위순회를 하는 순서는 다음과 같습니다.

전위순회(루트 노드를 가장 먼저 방문): A -> B -> C -> D -> E -> F -> G

public static void preOrder(Node root) {
        // base condition
        if (root == null) {
            return;
        }
        
        visited.add(root.value);
        preOrder(root.left);
        preOrder(root.right);

    }

중위순회: C -> B -> D -> A -> F -> E -> G

public static void inOrder(Node root) {
        // base condition
        if (root == null) {
            return;
        }
        
        inOrder(root.left);
        visited.add(root.value);
        inOrder(root.right);
        
    }

후위순회: C -> D -> B -> F -> G -> E -> A

public static void postOrder(Node root) {
        // base condition
        if (root == null) {
            return;
        }
        
        postOrder(root.left);
        postOrder(root.right);
        visited.add(root.value);
        
    }

⏰전위, 중위, 후위순회의 시간복잡도는 모든 노드를 방문해서 재귀 함수 호출 수 N개 x 재귀 함수 당 시간복잡도는 return문인 상수이므로 O(N * 1) = O(N)이 된다.