题目链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
难度：中等

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

题解

  1. from collections import deque
  2. # Definition for a binary tree node.
  3. # class TreeNode:
  4. #     def __init__(self, val=0, left=None, right=None):
  5. #         self.val = val
  6. #         self.left = left
  7. #         self.right = right
  8. class Solution:
  9.     def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
  10.         ret = []
  11.         if not root:
  12.             return ret
  14.         q = deque()
  15.         q.append(root)
  16.         level = 1
  17.         while q:
  18.             size = len(q)
  19.             cur_level = []
  20.             while size > 0:
  21.                 temp_node = q.popleft()
  22.                 cur_level.append(temp_node.val)
  23.                 if temp_node.left is not None:
  24.                     q.append(temp_node.left)
  25.                 if temp_node.right is not None:
  26.                     q.append(temp_node.right)
  27.                 size -= 1
  28.             if level & 1 == 1:
  29.                 ret.append(cur_level)
  30.             else:
  31.                 ret.append(cur_level[::-1]) # 这样要简单一点
  32.             level += 1
  33.         return ret