题目描述

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

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

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

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

我的解法——bfs（AC）

bfs+逆序
注意：不是每层都需要旋转。当它是奇数时将该层的元素逆序，当它是偶数时则不作改变。
时间复杂度O(n)，空间复杂度O(n)
Beat 57%

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if(root is None):
            return []
        
        res = []
        temp = []
        next_temp = []
        this_num = 0
        
        while(True): # 树
            if(this_num == 0 and temp == []):
                temp = [root]
            else:
                res.append([])
                next_temp = []
                for node in temp:
                    if(node):
                        res[this_num].append(node.val)
                    if(node.left):
                        next_temp.append(node.left)
                    if(node.right):
                        next_temp.append(node.right)
                if(this_num % 2 == 1):# 注意这里，不是每层都需要旋转
                    res[this_num] = res[this_num][::-1]
                
                temp = next_temp
                this_num += 1
            print(len(temp))
            if(len(temp) == 0):
                break

        return res

参考答案

https://blog.csdn.net/crazy1235/article/details/51524241