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

例如：
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回锯齿形层次遍历如下：

[
  [3],
  [20,9],
  [15,7]
]
通过次数80,081提交次数145,135

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""
from typing import *


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


class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        rtn, cur_list, q, count_level = [], [], [(root, 0)], 0
        while len(q) > 0:
            cur_node, cur_level = q.pop()
            if count_level == cur_level:
                cur_list.append(cur_node.val)
            else:
                count_level += 1
                rtn.append(cur_list)
                cur_list = [cur_node.val]

            if cur_node.left:
                q.insert(0, (cur_node.left, cur_level + 1))
            if cur_node.right:
                q.insert(0, (cur_node.right, cur_level + 1))

        rtn.append(cur_list)
        for i in range(1, len(rtn), 2):
            rtn[i].reverse()
        return rtn
