【LeetCode】103. 二叉树的锯齿形层序遍历

1.题目

2.思想

(1)层次遍历，只需要在输出的时候，调整一下就ok。 如果在输入的时候就调整，会引来整个序列的变化，导致不可控
(2)数据结构queue的使用。
对于常见的数据结构和函数，我们要牢记于心。比如翻转一个list，可以使用 reversed 方法，但是它并非是就地翻转。

3.代码

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
import copy
from queue import Queue
class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:        
        res = []
        if root is None:
            return res
        que = Queue() # 定义一个队列
        cnt = 0
        tmp = [root]        
        while(len(tmp)):            
            for i in range(len(tmp)):# 将temp中的元素逐个放入到que中 
                que.put(tmp[i])
            tmp.clear() 
            cur_res = [] # 当前这层的节点值
            while(que.qsize()): # 判断que中的内容 
                cur = que.get() # 获取头元素
                # print(cur.val,hight)
                if cur.left is not None:
                    tmp.append(cur.left)
                if cur.right is not None:
                    tmp.append(cur.right)
                cur_res.append(cur.val) # 很奇怪为啥这么会报错？
            if cnt % 2==1:
                cur_res= list(reversed(cur_res))
            res.append(copy.deepcopy(cur_res))
            cnt+=1
        return res