LeetCode : 102. Binary Tree Level Order Traversal

문제

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

 

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• 1000 <= Node.val <= 1000

 

풀이

1. 자식 노드들을 q에 담고, 그 순서로 조회하면서 BFS를 구현

 

2. 같은 레벨의 값들을 하나의 리스트(sublist)에 담아서 answer로 반환함

1. 이전 레벨의 값들의 조회가 끝나면, 새로운 sublist를 만듦
2. q의 크기인 l을 구하고, 그만큼 요소들을 sublist에 추가
3. 그 요소들은 같은 레벨의 값을 가짐

예시)

root = [1, 2, 3, 4, null, 5, 6] 이러한 상황일 때

1. q = [1] 일 때, l = 1, _ = 0
   1. 새로운 sublist 만들기
   2. cur = 1, sublist1 = [1]
2. q = [2, 3] 일 때, l = 2, _ = 0
   1. 새로운 sublist 만들기
   2. cur = 2, sublist2=[2]
3. q = [3, 4] 일 때, l = 2, _ = 1
   1. cur = 3, sublist2=[2, 3]
4. q = [4, 5, 6] 일 때, l = 3, _ = 0
   1. 새로운 sublist 만들기
   2. cur = 4, sublist3=[4]

 

시간복잡도 : O(n)

공간복잡도 : O(n)