[Leetcode/Python] Binary Tree Level Order Traversal

Top Interview Questions 의 Easy Collection에 있는 문제입니다.         
문제는 여기서 볼 수 있습니다.

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

 

이진 트리가 input으로 주어지면 같은 레벨에 있는 노드들을 하나의 리스트로 만들어 이중리스트를 output으로 도출하는 문제입니다.

 

Code:

# 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]]:
        if not root: return root
        answer, curr_level = [], [root]
        
        while curr_level:
            answer.append([node.val for node in curr_level])
            next_level = []
            for node in curr_level:
                if node.left: next_level.append(node.left)
                if node.right: next_level.append(node.right)
            curr_level = next_level[:]
        return answer

참고

 

풀이 설명:

1. root가 비었으면, 즉 [ ]라면, 그대로 리턴한다.

2. root가 비어있지 않다면, 정답 리스트를 만들고, 같은 레벨의 노드들을 처리할 리스트 [root]를 만든다. root는 매개변수로 전달받은 인자이다.

3. curr_level이 빌 때까지, 즉 각 레벨의 노드들이 모두 존재하지 않는 경우가 발생할 때까지, 끝 레벨까지 탐색한다.

4. answer 리스트에 한 레벨에 존재하는 모든 노드 값을 저장한다.

5. 다음 레벨을 탐색하고 정답리스트에 담기 위한 리스트를 생성한다.

6. 현재 레벨의 노드들을 for문으로 탐색하여 각 좌우를 확인하고 next_level에 넣는다.(다음 loop에서 노드의 val을 리스트에 담고, 좌우 자식 노드를 확인하는 목적)

7. 탐색할 다음 노드들이 담긴 next_level 리스트를 curr_level로 옮겨 다음 루프에서 확인한다.

8. 만약 next_level이 비었다면 현재의 curr_level이 마지막 레벨이므로 while문을 빠져나오게 된다.