题目：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,#,#,15,7},
3
/
9 20
/
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
思路：维护两个栈，一个放奇数行，一个放偶数行，同时注意奇偶压栈的顺序。初始时根在奇数栈，弹出元素并将左右孩子压入偶数栈，然后从偶数栈弹出，再将弹出元素的左右孩子压入奇数栈，直至两个栈都空。
代码：
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
result = []
stack1 = [root]
stack2 = []
if root is None:
return result
while len(stack1)!=0 or len(stack2)!=0:
if len(stack1) != 0:
result.append([node.val for node in stack1 if node is not None])
while len(stack1) != 0:
node = stack1.pop()
if node is not None and node.right != None:
stack2.append(node.right)
if node is not None and node.left != None:
stack2.append(node.left)
if len(stack2) != 0:
result.append([node.val for node in stack2 if node is not None])
while len(stack2) != 0:
node = stack2.pop()
if node is not None and node.left != None:
stack1.append(node.left)
if node is not None and node.right != None:
stack1.append(node.right)
return result
