给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]示例 2：
输入：root = [1]
输出：[[1]]示例 3：
输入：root = []
输出：[]# 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: TreeNode) -> List[List[int]]:# 方法一 使用队列if not root:return []queue = [root]res = []while queue:tmp = []size = len(queue)for _ in range(size):root = queue.pop(0)tmp.append(root.val)if root.left:queue.append(root.left)if root.right:queue.append(root.right)res.append(tmp)return res# 方法二 使用递归if not root:return []res = []def dfs(index, r):# 假设res是[[1],[2,3]], index是3， 再插入一个空list放到res中if len(res) < index:res.append([])# 将当前节点的值加入到res中，index表示当前层，假设index是1， 节点值为99# res是[[1],[2,3],[4]], 加入后res就变为了[[1],[2,3],[4,99]]res[index-1].append(r.val)# 递归的处理左子树，右子树，同时将层数index + 1if r.left:dfs(index + 1, r.left)if r.right:dfs(index + 1, r.right)dfs(1, root)return res