130、二叉树的之字形层序遍历

leetcode103
思路1：

• 打算建立两个队列L1，L2，用BFS方法去搜索，
• 当前列表设置为L1，然后搜索L1的节点，搜索一个就弹出一个，并把搜到的节点都添加到L2中
• 搜索完L1以后，此时L1为空，L2代表的是下一层的节点。此时再把当前队列设置为L2，然后进行上面的循环。
• 循环结束条件，两个list都为空时，说明循环就可以停止了。

思路2：

• 为了使代码简单些，把读取下一行，把下一行节点插入队列，读取下一行节点的val步骤单独定义成一个函数。
• 每次对新的一行进行搜索时，调用此函数即可，然后决定是否反转。
• 循环结束条件：新的队列为空

代码：
注意用列表表示队列时，每次添加元素都是用insert方法。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """

        def search_func(Q_para):
            Q_res = []
            L_res = []
            while Q_para:
                node = Q_para.pop()
                if node.left:
                    Q_res.insert(0,node.left)
                    L_res.append(node.left.val)
                if node.right:
                    Q_res.insert(0,node.right)
                    L_res.append(node.right.val)
            return Q_res,L_res
        if root:
            results = []
            Que = [root]
            L1 = [root.val]
            n = 0
            while Que:
                if n%2 == 0:
                    results.append(L1)
                else:
                    L1.reverse()
                    results.append(L1)
                Que,L1 = search_func(Que)
                n += 1
            return results
            
        else:
            return []