[HackerRank] Tree: Level Order Traversal

1. 문제

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

 

2. 풀이

처음에 preOrder 문제로 잘 못 생각한 문제. 레벨을 기준으로 순회를 해야한다.

아래 코드는 preOrder 코드

def levelOrder(root):
    if root is None:
        return
    print(root.info)
    levelOrder(root.left)
    levelOrder(root.right)

 

레벨 기준으로 순회하려면 BFS 와 같이 queue를 사용해야한다.

다른 사람 풀이를 보니 stack 과 queue 의 장점을 모두 가지고 있는 deque를 사용해서 deque 를 사용해서 해결한다.

 

queue 의 insert 연산은 index와 data 값 2개의 파라미터를 요구한다.

시간복잡도는 O(N) 이므로 이보다 시간복잡도가 더 작은 O(1) 의 deque 를 사용하는 것을 추천한다.

deque를 사용하려면 from collections import deque 선언이 필요하다.

 

- 아래는 동일한 코드!

queue.insert(0, data) => O(N)

deque.appendleft(data) => O(1)

 

3. 코드

방법 1) queue 사용

def levelOrder(root):
    if root is None:
        return
    if not root:
        return None
        
    queue = [root]
    
    while queue:
        cur = queue.pop()
        print(str(cur.info) + " ", end = "")
        if (cur.left is not None):
            queue.insert(0, cur.left)
        if (cur.right is not None):
            queue.insert(0, cur.right)

 

방법 2) deque 사용

from collections import deque

def levelOrder(root):
    if root is None:
        return
    if not root:
        return None
        
    queue = deque([root])
    
    while queue:
        cur = queue.pop()
        print(str(cur.info) + " ", end = "")
        if (cur.left is not None):
            queue.appendleft(cur.left)
        if (cur.right is not None):
            queue.appendleft(cur.right)

 

 

----

deque 개념: https://chaewonkong.github.io/posts/python-deque.html