力扣 二叉树的层序遍历

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

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