题目
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。即逐层地，从左到右访问所有节点。
例：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
方法：递归
递归部分的实现：
- 首先，判断此时的节点是否存在，若不存在，则直接返回空
- （因为记录结果的列表的记录方式为列表的不断嵌套，同一层的所有结点的值放在同一个列表中；同时，又因为我们将二叉树的深度从零开始，所以当进入一个新的深度时，此时记录结果的列表的长度是等于该层的深度的。）判断此时记录结果的列表长度是否等于此时需要遍历的层的深度，若相等，则表示此时为第一次遍历该层，所以在原始列表中嵌套新的列表
- 添加中间节点至此时深度的列表
- 若该中间节点存在左孩子，则使该左孩子作为新的中间节点开始新一轮递归
- 若该中间节点存在右孩子，则使该右孩子作为新的中间节点开始新一轮递归
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def levelOrder(self, root):
result = []
def DFS(root, depth):
if not root:
return
if len(result) == depth:
result.append([])
result[depth].append(root.val)
if root.left:
DFS(root.left, depth + 1)
if root.right:
DFS(root.right, depth + 1)
DFS(root, 0)
return result
相关知识
-
深度优先遍历 Depth First Search （DFS）：
对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次
