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

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

---

题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/

题目

---

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

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

    3
   / \
  9  20
    /  \
   15   7

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

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

解题思路

---

思路：广度优先搜索

这道题跟普通的二叉树层序遍历不同的是，要求返回节点值的锯齿形层序遍历。

其中锯齿形层序遍历的说明如下：

• 先从左往右，再从右往左进行下层遍历，以此类推，层与层之间交替进行。

根据上面的概念以及题目的示例，假设开始根节点这一层为第 0 0 0 层，这里的遍历顺序为从左到右，下一层为第 1 1 1 层，遍历的顺序则变为从右到左。也就说可以根据层数的奇偶来辨别此时遍历的方向。

这里我们还是使用广度优先搜索的思路，逐层进行遍历。但是这里为了能到达到锯齿形式的交替输出结果，这里借助双端队列来实现。具体的思路如下：

• 先处理特殊情况，当根节点 r o o t root root 为空时，返回空列表。

• 一般情况，声明队列 q u e u e queue queue，先将根节点存放进去。同时声明变量 i s _ e v e n _ l e v e l is\_even\_level is_even_level 用来标记当前层是偶数层还是奇数层，由此来辨别遍历的方向。其中 T r u e True True 表示当前层为偶数层， F a l s e False False 表示奇数层。

• 当队列不为空时，定义双端队列 l e v e l _ q u e u e level\_queue level_queue，同时求队列 q u e u e queue queue 的长度 s i z e size size。然后从队列 q u e u e queue queue 取出 s i z e size size 个元素进行处理：

  • 如果 i s _ e v e n _ l e v e l is\_even\_level is_even_level 为 T r u e True True 时，表示从左往右遍历，那么将当前遍历的元素插入到双端队列 l e v e l _ q u e u e level\_queue level_queue 末尾；
  • 如果 i s _ e v e n _ l e v e l is\_even\_level is_even_level 为 F a l s e False False 时，表示从右往左遍历，此时将当前遍历的元素插入到双端队列的头部。

• 插入元素同时需要将下一层的节点存放到 q u e u e queue queue 中。

• 每层遍历后，将当前层的遍历结果存放到返回列表 a n s ans ans（其中需要注意部分看代码实现处注释），同时注意更新维护 i s _ e v e n _ l e v e l is\_even\_level is_even_level 的值。

• 遍历结束后，返回 a n s ans ans。

具体的代码实现如下。

# 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: TreeNode) -> List[List[int]]:
        # 特殊情况处理
        if not root:
            return []        
        # queue 队列先存入根节点
        queue = deque()
        queue.append(root)
        
        # 用来标记当前层是偶数层还是奇数层
        is_even_level = True
        # 结果列表
        ans = []
        
        # 队列不为空时，开始进行遍历
        while queue:
            # 声明双端队列 level_queue
            level_queue = deque()
            # 先计算 queue 的长度 size
            size = len(queue)
            
            # 取出 size 个元素
            for _ in range(size):
                # 取出节点
                node = queue.popleft()
                # 偶数层，将节点值插入到 level_queue 尾部
                if is_even_level:
                    level_queue.append(node.val)
                # 奇数层，将节点值插入到 level_queue 头部
                else:
                    level_queue.appendleft(node.val)
                # 将下一层的节点存放到 queue 中
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            # 这里注意，将双端队列转换为列表的形式，存入结果列表中
            ans.append(list(level_queue))
            # 维护更新 is_even_level
            is_even_level = not is_even_level
        
        return ans

欢迎关注

---

公众号 【书所集录】

---

如有错误，烦请指出，欢迎指点交流。如果觉得写得还可以，还请麻烦点个赞????，谢谢。