[daiy5] jz77 print binary tree in zigzag order

subject ：

Given a binary tree , Returns the zigzag of the binary tree ,（ The first floor is from left to right , The next floor is from right to left , All the time ）

Ideas ：

The first idea to get the title is – Use queue , Things stored in odd and even are different ; It won't work ...
Later, I thought of using bilateral queues , According to the situation, which side goes in and out , Find no rules ...

Looking at the answer , It is found that two stacks are used ; There are also queues , Just print it backwards every other layer
according to reverse The idea of , It took me twenty minutes to write the code ：

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

answer ：

Double stack （ I didn't see clearly ）：

import copy
class Solution:
    def Print(self , pRoot: TreeNode) -> List[List[int]]:
        head = pRoot
        res = []
        if not head:
            #  If it's empty , Then return to null directly list
            return res 
        s1, s2 = [], []
        #  Put it in for the first time 
        s1.append(head) 
        while s1 or s2:
            temp = []
            #  Traverse odd layers 
            while s1: 
                node = s1[-1]
                #  Record odd layers 
                temp.append(node.val)
                #  Children of odd layers join even layers  
                if node.left: 
                    s2.append(node.left)
                if node.right:
                    s2.append(node.right)
                s1.pop()
            #  Only add when the array is not empty 
            if len(temp):  
                res.append(copy.deepcopy(temp))
            #  Clear the data of this layer 
            temp.clear() 
            #  Traverse even layers 
            while s2: 
                node = s2[-1]
                #  Record even layers 
                temp.append(node.val) 
                #  Children of even layers join odd layers 
                if node.right: 
                    s1.append(node.right)
                if node.left:
                    s1.append(node.left)
                s2.pop()
            if len(temp):
                res.append(temp)
        return res