leetcode:

https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/

github:

https://github.com/pythonkd/python/blob/master/LeetCode/zigzagLevelOrder.py

第一种采用队列和树的层次遍历

　　使用一个判断值每次遍历一层之后把该值变成原先的相反数

1 # Definition for a binary tree node. 2 # class TreeNode(object): 3 #     def __init__(self, x): 4 #         self.val = x 5 #         self.left = None 6 #         self.right = None 7 from collections import deque 8 class Solution(object): 9     def zigzagLevelOrder(self, root):10         """11         :type root: TreeNode12         :rtype: List[List[int]]13         """14         self.s = list()15         self.queue = deque()16         self.layer_trav(root)17         return self.s18     19     def layer_trav(self, subtree):20         if subtree:21             self.queue.append(subtree)22             target = 123             while self.queue:24                 tmp = list()25                 size = len(self.queue)26                 if target != 1:27                     while size > 0:28                         tree = self.queue.popleft()29                         tmp.insert(0, tree.val)30                         if tree.left:31                             self.queue.append(tree.left)32                         if tree.right:33                             self.queue.append(tree.right)34                         size -= 135                             36                 else:37                      while size > 0:38                         tree = self.queue.popleft()39                         tmp.append(tree.val)40                         if tree.left:41                             self.queue.append(tree.left)42                         if tree.right:43                             self.queue.append(tree.right)44                         size -= 145                             46                 self.s.append(tmp)47                 target = -target

时间是：28ms

第二种：是使用列表和层序遍历。然后再把列表中每层奇数次反转。

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Nonefrom collections import dequeclass Solution(object):    def zigzagLevelOrder(self, root):        """        :type root: TreeNode        :rtype: List[List[int]]        """        self.s = list()        self.queue = deque()        self.layer_trav(root)        for i, j in enumerate(self.s):            if i%2 != 0:                j.reverse()        return self.s        def layer_trav(self, subtree):        if subtree:            self.queue.append(subtree)            while self.queue:                tmp = list()                size = len(self.queue)                while size > 0:                    tree = self.queue.popleft()                    tmp.append(tree.val)                    if tree.left:                        self.queue.append(tree.left)                    if tree.right:                        self.queue.append(tree.right)                    size -= 1                self.s.append(tmp)