Tree: Level Order Traversal

이진 트리를 레벨 순서(또는 너비 우선)로 순회하고, 각 레벨의 노드 값을 순차적으로 출력하는 문제입니다. 이 문제는 이진 트리를 레벨마다 순회하여 레벨 별로 노드 값을 출력하는 방법을 구현하는 것이 목표입니다.

레벨 순서 순회(Level Order Traversal)란 루트 노드에서부터 시작하여 레벨 1부터 차례대로 아래로 내려가며 노드를 방문하는 방법입니다. 각 레벨에서 왼쪽에서 오른쪽 순서로 노드를 방문합니다. 즉, 레벨 1의 노드를 모두 방문한 후에 레벨 2의 노드를 방문하고, 레벨 2의 노드를 모두 방문한 후에 레벨 3의 노드를 방문하는 식으로 계속 진행됩니다.

문제의 입력으로는 이진 트리가 주어지며, 출력으로는 레벨 순서 순회 결과인 노드 값들을 순차적으로 반환하는 것이 요구됩니다. 이를 위해 주로 큐(Queue) 자료구조를 사용하여 레벨 순서 순회를 구현합니다.

예를 들어, 다음과 같은 이진 트리가 주어진다고 가정해보겠습니다:

 

    1
   / \
  2   3
 / \
4   5

 

이 트리를 레벨 순서로 순회하면, 결과는 다음과 같이 됩니다: 1 2 3 4 5

 

 void levelOrder(Node * root) {
        queue<Node*> q;
        q.push(root);
        while(!q.empty()){
            Node* current = q.front();
            q.pop();
            
            cout<<current->data<<" ";
            if(current->left){
                q.push(current->left);
            }
            if(current->right){
                q.push(current->right);
            }
        }
    }