6/22/2017 - 4:19 AM

## 103. Binary Tree Zigzag Level Order Traversal

1. Binary Tree Zigzag Level Order Traversal
``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if root == None:
return []
self.res = []
self.DFS(root, 1, True)
return self.res
def DFS(self, node, level, left2Right):
if node == None:
return
if len(self.res) < level:
self.res.append([])
if left2Right:
self.res[level-1].append(node.val)
else:
self.res[level-1].insert(0, node.val)
self.DFS(node.left, level+1, not left2Right)
self.DFS(node.right, level+1, not left2Right)``````

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/#/description

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]`,

``````    3
/ \
9  20
/  \
15   7
``````

return its zigzag level order traversal as:

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