给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
思路：这道题要求将树每一层的值存一个列表，所有层的列表存一个列表中
所以使用BFS(广度优先)，逐层遍历（同时确定遍历的层数）是可行的
同时DFS(深度优先)，可以使用字典记录 层数：[数值]。也是可行的
1.BFS模板
遍历时不用明确层数
我要评论while queue:
cur=queue.popleft()
'''取出节点'''
'''对此节点遍历'''
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
'''下一层非空结点加入队列'''
遍历时要求明确层数(每次while循环，一层个结点)
while queue:
size=len(queue)
for i in range(size):
'''遍历本层'''
cur=queue.popleft()
'''取出节点'''
'''对此节点遍历'''
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
'''下一层非空结点加入队列'''
代码
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
queue = collections.deque()
queue.append(root)
lt=[]
if not root:
return []
while queue:
size=len(queue)
l=[]
while size:
size-=1
cur=queue.popleft()
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
l.append(cur.val)
if l!=[]:
lt.append(l)
return lt
2.DFS代码
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
dt={}
def dg(root,n,dt):
if not root:
return
if not dt.get(n):
dt[n]=[root.val]
else:
dt[n].append(root.val)
dg(root.left,n+1,dt)
dg(root.right,n+1,dt)
dg(root,1,dt)
return list(dt.values())
本文地址：https://blog.csdn.net/honglouyibeng/article/details/107109822
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
荐 python知识点：函数参数、迭代器、生成器、装饰器、函数式变成、map/reduce、filter、sorted、继承和多态
qt designer 关于多页面跳转之后同一个页面出现多次的问题
网友评论