103. Binary Tree Zigzag Level Order Traversal

Binary Tree Zigzag Level Order Traversal - LeetCode

이진트리가 주어진다.

root level을 0이라고 했을 때 0, 2, 4, 6,.... 레벨의 노드는 왼쪽에서 오른쪽으로 순회하고,

1, 3, 5, 7,... 레벨의 노드는 오른쪽에서 왼쪽으로 순회한 결과를 반환하는 문제다.

 

1. Deque, BFS를 사용한 풀이

from typing import *
from collections import deque, defaultdict


class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        level = 0
        q = deque([(root, level)])
        seq = deque([(root.val, level)])
        while q:
            cur_node, cur_level = q.popleft()
            if cur_node.left:
                seq.append((cur_node.left.val, cur_level + 1))
                q.append((cur_node.left, cur_level + 1))
            if cur_node.right:
                seq.append((cur_node.right.val, cur_level + 1))
                q.append((cur_node.right, cur_level + 1))
        answer = []
        while seq:
            cur_val, cur_level = seq.popleft()
            temp = [cur_val]
            while seq and seq[0][1] == cur_level:
                temp.append(seq.popleft()[0])
            if cur_level % 2 == 0:
                answer.append(temp)
            else:
                answer.append(temp[::-1])
        return answer

BFS로 정직하게 왼쪽 노드부터 탐색하고 그 결과를 담는다.

여기서 결과를 담을 때 현재 노드의 level 정보를 같이 담는다.

Tree의 탐색이 끝난 후 결과를 앞에서부터 보면서 같은 레벨의 결과를 하나의 list에 묶고, 그 레벨 % 2가 0인 경우는 그냥 넣고, 0이 아닌 경우만 결과를 뒤집어서 최종 결과 list에 넣어줬다.