[Leetcode/파이썬] 102. Binary Tree Level Order Traversal

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).

 

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

 

Constraints:

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

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        q = deque()
        q.append(root)
        res = []

        while q :
            curr_lv = []
            for _ in range(len(q)) :
                curr_node = q.popleft()
                if curr_node :
                    curr_lv.append(curr_node.val)
                    q.append(curr_node.left)
                    q.append(curr_node.right)

            if curr_lv :
                res.append(curr_lv[:])

        return res

level 에 따라서 트리를 분류해보자. 너비우선탐색을 기반으로 접근을 해보자. 너비우선이기 때문에 같은 레벨에 있는 있는 노드들 부터 접근이 가능하다. 그럼 딱 같은 레벨의 노드까지만 접근이 가능할까? 이것은 while 문 안의 for문을 통해서 가능하다. queue의 길이만큼만 접근이 가능하다. 

현재 노드를 큐 가장 앞에 있는 곳에서 뽑아오고 현재 노드가 존재하면 현재 노드를 현재 레벨의 리스트에 저장, 왼쪽과 오른쪽에 있는 노드를 큐에 넣는다. 

현재 레벨의 리스트가 비어있지 않다면, res 리스트에 저장. 

이 문제는 문제의 흐름을 잘 파악하면 쉽게 접근이 가능하다. 저 for문을 유의하면서 문제를 풀어보면 좋을 듯 하다.