103. Binary Tree Zigzag Level Or

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

  [3],
  [20,9],
  [15,7]
]

First

树的层序遍历其实就是广度优先遍历，从第一层根节点开始，遍历所有第二层的节点。
将第二层的节点加入队列。然后继续遍历队列获取第三层的所有节点
题目还有一个条件需要Z字形遍历，其实可以根据每层的深度，对2取余获取是否该进行
倒转，若取余等于1，则进行倒转，否则不进行倒转

from quixote.structs.tree import TreeNode


class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        answer = []
        queue = [root]
        depth = 0
        while queue:
            tmp = []
            level = []
            for node in queue:
                if node.left:
                    tmp.append(node.left)
                if node.right:
                    tmp.append(node.right)
                level.append(node.val)
            queue = tmp
            if depth % 2:
                level = level[::-1]
            answer.append(level)
            depth += 1
        return answer

Fastest

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

class Solution(object):
    def zigzagLevelOrder(self, root):
        if not root:
            return []
        res = []
        depth = 0
        self.dfs(root, depth, res)
        return res

    def dfs(self, root, depth, res):
        if len(res) <= depth:
            res.append([])
        if depth % 2 == 0:
            res[depth].append(root.val)
        else:
            res[depth].insert(0, root.val)
        if root.left:
            self.dfs(root.left, depth + 1, res)
        if root.right:
            self.dfs(root.right, depth + 1, res)

作者虽然使用深度遍历，但通过判断每个节点的深度，将节点加入res数组对应子数组中