'''
leetcode 103. 二叉树的锯齿形层次遍历
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],

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

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

'''
# 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):
        if root is None:
            return []
        if root.left is None and root.right is None:
            return [[root.val]]
        flag=True
        queue=[]
        degree=[]
        queue.insert(0,root)
        degree.insert(0,1)
        last_degree=1
        temp=[]
        output=[]
        while(len(queue)>0):
            curr=queue.pop(-1)
            curr_degree=degree.pop(-1)
            if curr_degree==last_degree:
                temp.append(curr.val)
            else:
                if flag==False:
                    temp=temp[::-1]
                    flag=True
                else:
                    flag=False
                output.append(temp)
                last_degree=curr_degree
                temp=[curr.val]
            if curr.left is not None:
                queue.insert(0,curr.left)
                degree.insert(0,curr_degree+1)
            if curr.right is not None:
                queue.insert(0,curr.right)
                degree.insert(0,curr_degree+1)
        if flag==False:
            temp=temp[::-1]
        output.append(temp)
        return output

if __name__=="__main__":
    if __name__ == "__main__":
        root = TreeNode(3)
        root_l = TreeNode(9)
        root_r = TreeNode(20)
        root_r_l = TreeNode(15)
        root_r_r = TreeNode(7)

        root.left = root_l
        root.right = root_r

        root_r.left = root_r_l
        root_r.right = root_r_r

        print(Solution().zigzagLevelOrder(root))