반응형
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 == NULL) return; Data data; Queue q; QueueInit(&q); enqueue(&q, root); while(1){ data = dequeue(&q); if(data == NULL) break; 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
많이 부족합니다. 좋은 지적 부탁드립니다.
반응형
'<알고리즘 문제풀이&연습> > [C++] 백준, 프로그래머스 등등' 카테고리의 다른 글
[C++ 동적할당] Variable Sized Arrays (배열) (0) | 2017.07.08 |
---|---|
[C 자료구조] Stack - Balanced Brackets (0) | 2017.07.07 |
[C 자료구조] Linked Lists -Reverse a doubly linked list (1) | 2017.07.06 |
[C 자료구조] Heap - QHEAP1 (0) | 2017.07.05 |
[C 자료구조] Linked Lists - Reverse a linked list (0) | 2017.07.04 |
[C 자료구조] Linked Lists - Inserting a Node Into a Sorted Doubly Linked List (0) | 2017.06.29 |
[C 자료구조] Queue - Queue using Two Stacks (0) | 2017.06.27 |
[C 자료구조] Stack - Maximum Element (0) | 2017.06.26 |