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

解题思路：初步分析问题，需要使用层次遍历。因为遍历的顺序每一层都相反，设置一个flag来整除2，能整除则从左到右，否则从右到左，每次执行完一层将flag+1。逆序层次遍历需要注意：使用栈的思想（先进先出），优先遍历右子树.为了统一，节点入队均从末尾入队（使用append）

-- coding:utf-8 --

class TreeNode:

def init(self, x):

self.val = x

self.left = None

self.right = None

class Solution:
def Print(self, pRoot):
# write code here
# 层次遍历，队列
if not pRoot:
return []
flag = 2 # 用于决定层次遍历左右开始顺序，偶数为正序，奇数为逆序
res = [] # 存储最终返还结果
q = [] # 用来模拟队列
q.append(pRoot) # 根节点先入队

    # 当q队列为空时停止循环
    while q:
        temp = []    # 用于存储同一行的节点
        length = range(len(q))
        # 将q队列中的每一个节点均出队，并获取它的子节点
        # 这里需要实现“之”字形功能
        if flag % 2 == 0:
            for i in length:
                r = q.pop(0)    # 出队
                if r.left:
                    q.append(r.left)
                if r.right:
                    q.append(r.right)
                temp.append(r.val)

            flag = flag+1    # 下一次层次遍历顺序颠倒

        else:
            # q读取顺序相反，并且先读取右子树.先进先出（栈）
            for i in length:
                r = q.pop(-1)    # 出队
                if r.right:
                    # 借助insert()函数，将节点添加到q的首位
                    q.insert(0,r.right)
                if r.left:
                    q.insert(0,r.left)
                temp.append(r.val)

            flag = flag+1    # 下一次层次遍历顺序颠倒

        res.append(temp)

    return res