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

发表于 分类于 阅读次数：

解题思路

按层遍历二叉树即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        ret = []
        if not root:
            return ret
        
        is_from_left = True
        queue = collections.deque()
        queue.append(root)
        while queue:
            tmp_queue = collections.deque()
            val_list = []

            while queue:
                node = queue.popleft()
                if is_from_left:
                    val_list.append(node.val)
                else:
                    val_list.insert(0, node.val)

                if node.left:
                    tmp_queue.append(node.left)
                if node.right:
                    tmp_queue.append(node.right)

            ret.append(val_list)
            is_from_left = not is_from_left
            queue = tmp_queue
        return ret