题解 | #二叉树的之字形层序遍历#

'''
解题思路：
1、BFS广度优先搜索，先获得每一层需要输出节点的个数，再一个个减小到0，这一层输出结束后，再输出下一层
2、queue.insert(0, cur.left)，新增节点插入到0位
3、之字型：引入一个变量k记录奇偶层，层数从0开始，奇数层tmp.appe***al) 改成 tmp.insert(0,t.val)
'''
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
# 
# @param root TreeNode类 
# @return int整型二维数组
#
class Solution:
    def zigzagLevelOrder(self , root ):
        # write code here
        if not root:
            return None

        queue = [root]
        res = []
        k = 0
        while queue:
            n = len(queue)
            tmp = []
            while n>0:
                t = queue.pop()
                #print('k=',k)
                if k%2==0:
                    tmp.appe***al)
                else:
                    tmp.insert(0,t.val)
                if t.left:
                    queue.insert(0,t.left)
                if t.right:
                    queue.insert(0,t.right)
                n -= 1
            k += 1
            res.append(tmp)
        #print('res=',res)
        return res


root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
Solution().zigzagLevelOrder(root)