[LeetCode] Binary Tree Zigzag Level Order Traversal

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

 

For example:
Given binary tree [3,9,20,null,null,15,7],

 

return its zigzag level order traversal as:

[ [3], [20,9], [15,7] ]

 

Solution

1. root를 담은 q가 있는동안 반복한다.

2. q의 길이를 cnt로 놓고 cnt가 있는 동안 반복문을 실행한다.

3. q의 가장 첫번째를 pop하여 그 value값을 tmp에 담고, left또는 right가 있으면 그 값을 q에 담아 다음 depth도 처리한다.

4. cnt반복문이 한번 끝났을 경우 leftToRight로 왼쪽에서부터 결과를 담을지, 오른쪽에서부터 결과를 담을지 판단한다.

5. root가 없을경우 예외처리도 해준다.

#(6) Binary Tree Zigzag Level Order Traversal

# 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: TreeNode) -> List[List[int]]:
        if not root:
            return []
        result = []
        q = [root]
        leftToRight = True
        while q:
            tmp = []
            cnt = len(q)
            while cnt:
                node = q.pop(0)
                tmp.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
                cnt -= 1
            if leftToRight:
                result.append(tmp)
                leftToRight = False
            else:
                result.append(tmp[::-1])
                leftToRight = True
        return result