leetcode103.Binary Tree Zigzag Level Order Traversal

我又肥来复习了。
原题链接https://leetcode.com/problems/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],
3
/
9 20
/
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]

这里主要是考虑用两个栈，在各层分别从左至右，从右至左入栈。
比如第一行直接进栈stack1，然后开始遍历stack1，若非空则栈顶出栈，数据进入res1，同时将栈顶数据的额子节点入stack2,由于是zigzag式输出，此时入栈stack2要从左往右入栈，这样出栈时的数据才是从右往左输出。之后继续判断stack1是否为空，循环输出数据，直至stack1为空，之后判断res1是否空，将res1输入res。同理判断stack2，左右顺序与stack1相反，直至stack1和stack2均为空，输出res。

之所以有个栈命名为deques，是刚开始入栈顺序弄错了，想到了用一个队列结构 /手动滑稽。

class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        stack = []
        res = []
        deques = []
        deques.append(root)
        while (stack or deques):
            res1 = []
            while stack:
                item = stack.pop()
                res1.append(item.val)
                if item.right:
                    deques.append(item.right)
                if item.left:
                    deques.append(item.left)
            if res1:
                res.append(res1)
            res2 = []
            while deques:
                item = deques.pop()
                res2.append(item.val)
                if item.left:
                    stack.append(item.left)
                if item.right:
                    stack.append(item.right)
            if res2:
                res.append(res2)
        return res