[LeetCode] 103. Binary Tree Zigzag Level Order Traversal 풀이 및 코드

문제

레벨 별로 다른 순서(왼쪽->오른쪽, 오른쪽->왼쪽)로 이진 트리(Binary Tree)를 순회하라.

---

풀이

쉬울 줄 알았는데 생각보다 통과하기가 어려웠다. 

기본적인 알고리즘은 이전 포스트인 이진 트리를 BFS(너비 우선 탐색) 방식으로 레벨별로 순회하는 알고리즘과 비슷하다. (june-coder.tistory.com/16?category=913762)

[LeetCode] 102. Binary Tree Level Order Traversal 풀이 및 코드

단, 주의해야 할점은 레벨 별로 다른 순서로 순회하여야 한다는 점이다. 따라서 각 레벨별로 순회해야 하는 방향(isLeft)을 정해놓고 그 방향에 맞춰 순회해야 한다. 어려웠던 부분은 오른쪽에서 왼쪽으로 순회할때, 큐에는 왼쪽에서 오른쪽 순서로 저장해야 한다는 점이다.(리스트의 0번 인덱스에 아이템을 삽입하면 된다.) 그 이유는 다음 레벨에서 이전 레벨 리스트를 순회하는데 오른쪽에서 왼쪽으로 리스트가 저장되어 있으면 헷갈리기 때문이다. 이 부분만 유의한다면 코드를 짜기는 어렵지 않다.

---

코드

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return root
        
        binary_tree_list, queue = [[root.val]], [root]
        isLeft = False
        while len(queue) != 0:
            children, children_val = [], []
            if isLeft:
                while len(queue) != 0:
                    parent = queue.pop(0)           
                    if parent.left:
                        children.append(parent.left)
                        children_val.append(parent.left.val)
                    if parent.right:
                        children.append(parent.right)
                        children_val.append(parent.right.val)
                isLeft = False
            else:
                while len(queue) != 0:
                    parent = queue.pop()
                    if parent.right:
                        children.insert(0, parent.right)
                        children_val.append(parent.right.val)
                    if parent.left:
                        children.insert(0, parent.left)
                        children_val.append(parent.left.val)
                isLeft = True
                
            queue = children
            if children_val:
                binary_tree_list.append(children_val)
        return binary_tree_list

---

리트코드 제출 결과

LeetCode 제출 결과

---

출처

leetcode.com/problems/binary-tree-zigzag-level-order-traversal/