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

Binary Tree Zigzag Level Order Traversal

---

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

 

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[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].
• -100 <= Node.val <= 100

 

# 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 zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        q = deque()
        q.append(root)

        res = []
        d = 1

        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[::d])
                d *= -1

        return res

102. Binary Tree Level Order Traversal 과 유사한 문제. 

문제를 살펴보자. 우선 같은 레벨에 있는 노드들끼리 분리해서 저장하는 문제. 추가된 것은 배열 순서이다.

같은 레벨 분류는 while 문 안에 있는 for 문으로 하고, curr_lv 에 넣어준다. 

그리고 현재 노드가 존재하면 curr_lv[::d]를 하여 현재 노드에 대해 정배열을 할지 역배열을 할지 정한다. 초기값은 1, 이 단계를 행할 때 마다 d를 -1, 1 로 번갈아 가며 세팅될 수 있도록 d에 계속해서 -1을 곱하여 부호를 바뀌도록 한다. 

이 문제의 포인트는 현재 레벨을 어떻게 분류할 것인가. 또한 d 를 통하여 정배열, 역배열을 결정할 수 있다.