<알고리즘 문제풀이&연습>/[C,C++] Hackerrank

[C 자료구조] Tree - Level Order Traversal

사용자 BlockDMask 2017. 7. 5. 10:37
반응형

0) 제목

  • Hackerrank 의 Linked Lists 부분의 Reverse a linked list 문제입니다.

  • C언어를 이용하여 풀었습니다.

1) 문제 설명 

  • Tree의 Root Node의 Pointer가 Level Order 함수의 파라미터로 주어지고, 

  • 주어진 트리의 Level별로 data를 순서대로 출력하는 문제입니다.

2) 풀이 과정 

  • BFS(넓이 우선 탐색)라고 생각하여서 Queue를 이용해서 풀었습니다. 

  • 또한, 문제에서 주어진 Tree의 Node의 갯수가 최대 500 이어서, 

  • 동적할당을 이용한 Linked lists로 Queue를 구현하는 방식으로 풀었습니다.


3) 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/*
typedef struct _node
{
    int data;
    struct _node * left;
    struct _node * right;
} node*/
//BFS식. (queue 이용)
 
///////////////////////////////////Queue 구현////////////////////////////////
 
typedef node * Data;
 
typedef struct _qnode{
    Data data;
    struct _qnode *next;
} QNode;
typedef struct _queue{
    QNode * front;
    QNode * rear;
} Queue;
 
void QueueInit(Queue * pq){
    pq->front = NULL;
    pq->rear = NULL;
}
void enqueue(Queue * pq, Data data){
    QNode * newNode = (QNode *)malloc(sizeof(QNode));
    newNode->data = data;
    newNode->next = NULL;
    
    if(pq->front == NULL){
        pq->front = newNode;
        pq->rear = newNode;
    }else{
        pq->rear->next = newNode;
        pq->rear = newNode;
    }
}
Data dequeue(Queue * pq){
    if(pq->front == NULL){
        return NULL;
    }
    QNode * delNode = pq->front;
    Data data = delNode->data;
    pq->front = pq->front->next;
    
    free(delNode);
    return data;
}
 
//////////////////////////////////Level Order 함수////////////////////////////////////
 
void levelOrder(node * root) {
    if(root == NULLreturn;
    Data data;
    Queue q;
    QueueInit(&q);
    enqueue(&q, root);
    while(1){
        data = dequeue(&q);
        if(data == NULLbreak;
        printf("%d ", data->data);
 
        if(data->left != NULL){
            enqueue(&q, data->left);
        }
        if(data->right != NULL){
            enqueue(&q, data->right);
        }    
    }
}
cs


주석 내부에 있는 부분은 C언어 문법에 맞게 고쳤습니다.

(Hackerrank 에서는 C++ 문법으로 지원)

경로 : Dashboard>Data Structures>Tree>Level Order Traversal

출처 : [HackerRank] https://www.hackerrank.com/challenges/tree-level-order-traversal/problem

많이 부족합니다. 좋은 지적 부탁드립니다.


반응형