leetcode-103

103. 二叉树的锯齿形层序遍历

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],

  3
 / \
9  20
  /  \
 15   7

返回锯齿形层序遍历如下：

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

解法

在官方题解中，temp列表是双端队列。

class Solution:
    def zigzagLevelOrder(self, root: TreeNode):
        if not root:
            return []
        
        res = []

        floor = 0

        queue = list()
        queue.append(root)

        while queue:
            q_len = len(queue)
            temp = []
            for i in range(q_len):
                cur = queue.pop(0)
                temp.append(cur.val)

                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            if floor %2 == 0:
                res.append(temp)
            else:
                res.append(temp[::-1])
            floor += 1
        return res