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

发表于 | 分类于
字数统计: 213 | 阅读时长 ≈ 1

题目描述

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

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

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

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

1
2
3
4
5
[
  [3],
  [20,9],
  [15,7]
]

题解

思路

简单的二叉树层次遍历；

加一个flag标志，将奇数层的节点列表反转即可。

Python：

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
class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        from queue import Queue
        q = Queue()
        res = []
        if root == None:
            return res
        q.put(root)
        level = 0
        while not q.empty():
            n = q.qsize()
            level_list = []
            for i in range(n):
                cur = q.get()
                level_list.append(cur.val)

                if cur.left != None:
                    q.put(cur.left)
                if cur.right != None:
                    q.put(cur.right)
            if level % 2 == 1:
                level_list.reverse()
            print(str(level) + ":" + str(level_list))
            level += 1
            res.append(level_list)
        return res