# 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，
# 第三行按照从左到右的顺序打印，其他行以此类推。


# 思路：层序遍历二叉树，偶数行从右到左，奇数行从左到右
# 那么可以先层序遍历一次，然后按照上面的顺序打印
class Solution:
    def __init__(self):
        self.res = [[]]

    def Print(self, pRoot):
        self.get_level_tree(pRoot,1)
        isTurn = False
        result = []
        self.res.pop()
        for i in range(len(self.res)):
            if isTurn:
                self.res[i]=self.res[i][::-1]
            isTurn =  not isTurn

        return self.res

    # write code here

    def get_level_tree(self, my_root, level):
        if not my_root:
            return None
        else:
            self.res[level - 1].append(my_root.val)
            if len(self.res) == level:
                self.res.append([])
            self.get_level_tree(my_root.left, level + 1)
            self.get_level_tree(my_root.right, level + 1)