[牛客网刷题 Day5] JZ77 按之字形顺序打印二叉树

题目：

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

思路：

拿到题目的第一想法就是–使用队列呀，奇偶的时候存的东西不一样；行不通。。。
后来又想到使用双边队列，分情况从哪边进哪边出，发现找不到什么规律。。。

看了答案，发现用到了两个栈；也有使用队列，只不过每隔一层就反向打印一下
根据reverse的思路，我花了二十分钟写出来了代码：

class Solution:
    def Print(self, pRoot: TreeNode):
        # write code here
        if pRoot is None:
            return None
        res = []
        q = queue.Queue()
        q.put(pRoot)
        flag = 0

        while not q.empty():
            cur_res = []
            n = q.qsize()
            for i in range(n):
                node = q.get()
                cur_res.append(node.val)
                if node.left:
                    q.put(node.left)
                if node.right:
                    q.put(node.right)
            if flag % 2 != 0:
                cur_res.reverse()
            res.append(cur_res)
            flag = flag+1

        return res

答案：

双栈（没咋看明白）：

import copy
class Solution:
    def Print(self , pRoot: TreeNode) -> List[List[int]]:
        head = pRoot
        res = []
        if not head:
            # 如果是空，则直接返回空list
            return res 
        s1, s2 = [], []
        # 放入第一次
        s1.append(head) 
        while s1 or s2:
            temp = []
            # 遍历奇数层
            while s1: 
                node = s1[-1]
                # 记录奇数层
                temp.append(node.val)
                # 奇数层的子节点加入偶数层 
                if node.left: 
                    s2.append(node.left)
                if node.right:
                    s2.append(node.right)
                s1.pop()
            # 数组不为空才添加
            if len(temp):  
                res.append(copy.deepcopy(temp))
            # 清空本层数据
            temp.clear() 
            # 遍历偶数层
            while s2: 
                node = s2[-1]
                # 记录偶数层
                temp.append(node.val) 
                # 偶数层的子节点加入奇数层
                if node.right: 
                    s1.append(node.right)
                if node.left:
                    s1.append(node.left)
                s2.pop()
            if len(temp):
                res.append(temp)
        return res