###### tags: `Leetcode` `medium` `tree` `bfs` `python`

# 103. Binary Tree Zigzag Level Order Traversal

## [題目連結:] https://leetcode.com/problems/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).


#### [圖片來源:] https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

## 解題想法:
兄弟題目: [102. Binary Tree Level Order Traversal](/uzzm6rKYT0iLgackHNRl5A)

* 此題為求level-order，但是每一層的值要交替呈現
* 即第一行左到右、第二行右到左、第三行左到右....
* 設字典
* dic
* key: level
* val: list() for append node
* 判斷當前level為奇數or偶數
* root第一層:level=0
* 每次從que中pop最早進入的
* 判斷level:
* 若偶數: 新加入的node.val一律加到list**最右邊**
* 可以正常append
* 若奇數: 新加入的node.val一律加到list**最左邊**
* 用insert(0,node.val)
## Python:

from collections import defaultdict
class TreeNode():
    def __init__(self,val=0,left=None,right=None):
        self.val=val
        self.left=left
        self.right=right
    def insertLeft(self,node):
        if not self.left:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if not self.right:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)
        
class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        dic=defaultdict(list)
        que=[{'level':0,'node':root}]
        while que:
            #每次pop最左邊的: 3->9->20->15->7
            cur=que.pop(0)
            curLevel=cur['level']
            curRoot=cur['node']
            #若偶數: 新加入的node.val一律加到list**最右邊**
            if curLevel%2==0:
                dic[curLevel].append(curRoot.val)
            #若奇數: 新加入的node.val一律加到list**最左邊**
            else:
                dic[curLevel].insert(0,curRoot.val)
            if curRoot.left:
                que.append({'level':curLevel+1, 'node':curRoot.left})
            if curRoot.right:
                que.append({'level':curLevel+1, 'node':curRoot.right})
        return [ dic[key] for key in dic]

root=TreeNode(1)
root.insertLeft(2)
root.insertRight(3)
root.left.insertLeft(4)
root.left.insertRight(5)
root.right.insertLeft(6)
root.right.insertRight(7)
print('orignal tree:',end=' ')
root.printTree()

result = Solution()
ans = result.zigzagLevelOrder(root)
print(ans)