[알고리즘 연습] 이진트리 깊이별로 나누기

이진트리 깊이별로 나누기

• 이진트리의 root노드를 파라미터로 주었을 때 그를 기반으로 깊이별 요소들을 각각 리스트로 저장해 가지는 이차원 리스트를 리턴해라

---

import queue

class Node():
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        
def printTree(node):
    all_lines = []
    line = []

    q = queue.Queue()
    q.put(node)
    q.put(Node(-1))

    while q.qsize() > 0:
        node = q.get()        
        if not node:
            continue
        else:
            if node.val == -1: # 새 리스트 생성
                if q.qsize() > 0:
                    all_lines.append(line)
                    line = []
                    q.put(Node(-1))
            else:
                line.append(node.val)
                q.put(node.left)
                q.put(node.right)
    return all_lines    

   1
 2   3
4 5 6 7 
==위 형태의 트리구조의 root노드를 파라미터에 넣어줬을 때 결과==
[[1], [2,3], [4,5,6,7]

• 저장된 데이터로부터 값을 순서대로 가져와야 하지만 그 값을 바로바로 처리할 순 없고, 순서는 유지해야할 때 큐나 스택을 사용하는 방법을 고민해볼 필요가 있다.
• BFS, DFS 적용에 익숙해지자
• 큐와 스택을 저장한 순서를 유지하여 '가장 먼저 넣어줬던 값' 혹은 '가장 최근에 넣어줬던 값'을 활용할 수 있도록 해준다.
• 해당 문제에선 각 깊이별로 구분이 필요했기 때문에 -1값을 가지는 노드로 그를 구분했다. (물론 다른 방법을 사용해도 상관없다.)