数据结构（二叉树的层序遍历）

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

思路：这道题要求将树每一层的值存一个列表，所有层的列表存一个列表中
所以使用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