526互联

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

发布时间 2023-12-22 16:00:33作者: Frommoon

目录

题目

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

题解：BFS

  • 用BFS把每一层的结点存在一个列表里面，然后判断一下如果是偶数层就翻转列表，最后都加入结果列表返回即可
class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
         if not root:# 如果根节点为空，直接返回空列表
             return []
         q = []  # 用一个列表做队列
         re = [] # 存储结果的列表
         q.append(root)  # 把起点放入队列
         step = 1   # 记录当前层的编号
         while q:  # 当队列不为空时
             size = len(q)
             re1=[]# 存储当前层的结果
             # 将当前队列中的所有节点向四周扩散
             for _ in range(size):
                 cur = q.pop(0)  # 从头部取出节点
                 re1.append(cur.val) # 将当前节点的值加入当前层的结果列表
                 if cur.left is not None:
                     q.append(cur.left) # 将左子节点加入队列
                 if cur.right : # 将cur的相邻节点加入队列 
                     q.append(cur.right) # 将右子节点加入队列
                     
             if step%2==0:# 如果当前层的编号为偶数，将结果列表反转
                re1.reverse() 
             re.append(re1) # 将当前层的结果列表加入最终结果列表
             step += 1  # 增加步数
         return re