C++로 구현하는 N-ary 트리 전위 순회(Preorder Traversal)

n-ary 트리(N-ary Tree)가 하나 주어졌을 때, 모든 노드의 전위 순회(preorder traversal) 결과를 구하는 문제입니다.

예를 들어 아래와 같은 트리가 입력으로 주어진다면,

출력은 [1, 3, 5, 6, 2, 4]가 됩니다.

풀이 접근 방법

전위 순회는 루트를 먼저 방문한 뒤, 각 자식 노드를 왼쪽에서 오른쪽 순서로 재귀적으로 방문하는 방식입니다. 이 개념을 바탕으로 다음 단계로 문제를 해결할 수 있습니다.

• 순회 결과를 저장할 배열 ans를 정의합니다.
• preorder() 메서드를 정의하며, 이 메서드는 루트 노드를 인자로 받습니다.
• 루트가 null이라면 빈 리스트를 반환합니다.
• 현재 루트 노드의 값을 ans의 끝에 추가합니다.
• 루트의 children 배열에 있는 모든 자식 노드 i에 대해 preorder(i)를 재귀적으로 호출합니다.
• 모든 순회가 끝나면 ans를 반환합니다.

C++ 구현 예제

아래 코드를 통해 실제 동작 방식을 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i < v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) {
        val = _val;
    }
    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

class Solution {
public:
    vector<int> ans;
    vector<int> preorder(Node* root) {
        if (!root)
            return {};
        ans.emplace_back(root->val);
        for (auto i : root->children)
            preorder(i);
        return ans;
    }
};

main(){
    Solution ob;
    Node *node5 = new Node(5), *node6 = new Node(6);
    vector<Node*> child_of_3 = {node5, node6};
    Node* node3 = new Node(3, child_of_3);
    Node *node2 = new Node(2), *node4 = new Node(4);
    vector<Node*> child_of_1 = {node3, node2, node4};
    Node *node1 = new Node(1, child_of_1);
    print_vector(ob.preorder(node1));
}

입력

Node *node5 = new Node(5), *node6 = new Node(6);
vector<Node*> child_of_3 = {node5, node6};
Node* node3 = new Node(3, child_of_3);
Node *node2 = new Node(2), *node4 = new Node(4);
vector<Node*> child_of_1 = {node3, node2, node4};
Node *node1 = new Node(1, child_of_1);

출력

[1, 3, 5, 6, 2, 4]

정리

이 알고리즘은 각 노드를 정확히 한 번씩 방문하므로 시간 복잡도는 O(N)이며, 여기서 N은 트리의 전체 노드 수입니다. 공간 복잡도 역시 재귀 호출 스택과 결과 배열 때문에 최악의 경우 O(N)이 됩니다. 재귀 대신 스택(stack)을 사용하면 반복(iterative) 방식으로도 구현할 수 있으니, 심화 학습을 위해 도전해 보시길 권장합니다.