【BFS+DFS】102--层序遍历

首先对于BFS

重点：对队列的使用，一般是两个循环

# 队列不为空
while len(q) > 0:
  size = len(q)
  # 每层节点数量不为空
  while size > 0:
    # 实际操作
    # 添加队列
    size -= 1

实际代码如下，要多练：

对于DFS解法，这个题解解决了如何知道遍历到第几层！

具体操作：我们已知root是第一层，设置0层 level = 0，每次递归进去把 level + 1 放进参数表

# 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 root is None:
            return []
        retList = []

        self.dfs(root, retList, 0)
        return retList
    
    def dfs(self, root, retList, level):
        # 实际操作
        ## 当 retList 长度不够时，append一个[]
        if len(retList) < level + 1:
            retList.append([])
        ## 把节点元素放进对应的子列表中
        retList[level].append(root.val)


        # 终止条件
        if root.left is None and root.right is None:
            return


        # 递归拆解
        if root.left is not None:
            self.dfs(root.left, retList, level+1)
        
        if root.right is not None:
            self.dfs(root.right, retList, level+1)