难度: 中等(Medium)

题目：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