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

이진트리 깊이별로 나누기

• 이진트리의 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값을 가지는 노드로 그를 구분했다. (물론 다른 방법을 사용해도 상관없다.)