二叉树的锯齿形层次遍历

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

思路：逐层遍历，所以优先选择BFS(宽度优先)
如果正常顺序（统一从左到右）的话，可以先看这个二叉树的层序遍历

锯齿遍历的话，解题思路如下：
1.我们不改变进队列的顺序，下层一直按从左到右进队。
2.但我们会将 队列值的访问，进队出队 这两步分开操作。
3.即先将本层根据层数从左到右或从右到左访问。之后将本层节点出队，下层依然按照固定顺序入队

数据分析：
queue:它里面永远存且仅存 一层节点

class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        queue=collections.deque()
        queue.append(root)
        if not root:
            return []
        n=0
        lt=[]
        
        while queue:
            size=len(queue)
            n=(n+1)%2
            l=[]
            #根据n值，改变访问方向
            if n:
                for i in range(size):
                    l.append(queue[i].val)
            else:
                for i in range(-1,-size-1,-1):
                    l.append(queue[i].val)                
			#存入总列表
            if l:
                lt.append(l)
            #本层出队，下层按统一方向（从左到右）进队   
            for i in range(size):
                cur=queue.popleft()
                if cur.left:
                    queue.append(cur.left)                   
                if cur.right:
                    queue.append(cur.right)

        return lt

本文地址：https://blog.csdn.net/honglouyibeng/article/details/107112383