题解 | #牛群Z字型排列#

• 题目考察的知识点 : 二叉树的层次遍历
• 题目解答方法的文字分析：

1. 使用deque来模拟队列,存储每一层的节点。
2. 对于每一层,使用一个临时的deque来存储该层的节点值。
3. 判断当前是偶数层还是奇数层,如果是偶数层,则将节点值从左加到tmp deque;如果是奇数层,则将节点值从右加到tmp deque。
4. 遍历完一层后,将tmp deque转换成list添加到结果res中。
5. 最后将左右子节点加入下一层的deque中，通过控制从左或从右加入临时deque来实现Z字形层序遍历。

• 本题解析所用的编程语言：Python
• 完整且正确的编程代码

import collections
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型二维数组
#

from collections import deque
class Solution:
    def ZLevelOrder(self , root: TreeNode) -> List[List[int]]:

        if not root: 
            return []
        res = []
        deque = collections.deque()
        deque.append(root)

        while deque:
            tmp = collections.deque()
            for _ in range(len(deque)):
                node = deque.popleft()
                if len(res) % 2: tmp.appendleft(node.val) # 偶数层 -> 队列头部
                else: tmp.append(node.val) # 奇数层 -> 队列尾部
                if node.left: deque.append(node.left)
                if node.right: deque.append(node.right)
            res.append(list(tmp))
        return res