给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
思路：逐层遍历，所以优先选择BFS(宽度优先)
如果正常顺序（统一从左到右）的话，可以先看这个二叉树的层序遍历
锯齿遍历的话，解题思路如下：
1.我们不改变进队列的顺序，下层一直按从左到右进队。
2.但我们会将 队列值的访问，进队出队 这两步分开操作。
3.即先将本层根据层数从左到右或从右到左访问。之后将本层节点出队，下层依然按照固定顺序入队
数据分析：
queue:它里面永远存且仅存 一层节点
我要评论class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
queue=collections.deque()
queue.append(root)
if not root:
return []
n=0
lt=[]
while queue:
size=len(queue)
n=(n+1)%2
l=[]
#根据n值，改变访问方向
if n:
for i in range(size):
l.append(queue[i].val)
else:
for i in range(-1,-size-1,-1):
l.append(queue[i].val)
#存入总列表
if l:
lt.append(l)
#本层出队，下层按统一方向（从左到右）进队
for i in range(size):
cur=queue.popleft()
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
return lt
本文地址：https://blog.csdn.net/honglouyibeng/article/details/107112383
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
荐 python知识点：函数参数、迭代器、生成器、装饰器、函数式变成、map/reduce、filter、sorted、继承和多态
qt designer 关于多页面跳转之后同一个页面出现多次的问题
网友评论