按之字形顺序打印二叉树

题目描述

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

思路

最初的思路是利用宽度优先搜索，对树进行层次遍历。然后根据遍历的层次来控制每次输出的方向。比如奇数（假设从1开始）正向输出，偶数反向输出。
后续做了一点改进，省去了逆向输出这个操作。在层次遍历的时候，先判断当前是应该正向还是反向输出的层。如果是反向输出，那么把当前层的当前节点每次都插入到当前队列的最前面。这样可以保证，当遍历完这一层时，存在数组里的节点已经是逆向的。

代码

class Solution:
    def Print(self, pRoot):
        if pRoot is None:
            return []
        result = []
        q = [pRoot]
        flag = 1  #控制输出方向
        while q:
            current_level = []
            temp_result = []
            for node in q:
                if flag == 1:
                    temp_result.append(node.val)
                if flag == -1:
                    temp_result.insert(0,node.val) #把后续节点插入到起始部位
                if node.left is not None:
                    current_level.append(node.left)
                if node.right is not None:
                    current_level.append(node.right)
            result.append(temp_result)
            q = current_level
            flag = flag * -1 #反向
        return result