题目:
给你二叉树的根节点
root
,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。来源:力扣(LeetCode)
链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
示例:
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]
示例 2:输入:root = [1]
输出:[[1]]
示例 3:输入:root = []
输出:[]
解法:
BFS,记录层数,使用字典记录层对应的节点。
代码:
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution:def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:queue = [(0, root)]d = defaultdict(list)while queue:level, cur = queue.pop(0)if cur:d[level].append(cur.val)queue.append((level + 1, cur.left))queue.append((level + 1, cur.right))return list(d.values())