[HackerRank] Tree: Level Order Traversal

https://www.hackerrank.com/challenges/tree-level-order-traversal/problem

Tree: Level Order Traversal | HackerRank

Data Structures > Trees

 

트리가 주어지면 level order로 출력한다.

 

코드

struct node* queue[500];
int front = -1, rear = -1;

void addq(struct node *ptr){
    queue[++rear] = ptr;
}

struct node* deleteq(){
    return queue[++front];
}

void levelOrder(struct node *root) {
    if (!root) return;
    addq(root);
    while(1){
        root = deleteq();
        if (root){
            printf("%d ", root->data);
            if (root->left) addq(root->left);
            if (root->right) addq(root->right);
        }
        else break;
    }
}

 

설명

root가 NULL이면 그대로 리턴하고, 아니면 addq함수를 통해 root를 큐에 저장한다.

큐에서 노드를 하나 가져와 root에 저장하고, 만약 NULL이 아니면 해당 노드의 data를 출력한다.

만약 해당 노드의 왼쪽 또는 오른쪽 자식 노드가 NULL이 아니면 큐에 저장한다.

노드가 NULL이 아닐때까지 반복하고, 만약 NULL에 도달하면 break 한다.