【BFS+DFS】107 -- 层序遍历II

# 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 levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        retList = []
        level = 0
        self.dfs(root, retList, level)
        retList = self.reverseListTwoPoiters(retList)

        return retList

    def dfs(self, root, retList, level):
        # 实际操作
        ## 如果 retList 的长度不足时，要 append 一个空列表
        if len(retList) < level + 1:
            retList.append([])
        ## 添加进 retList
        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)
    
    def reverseListTwoPoiters(self, retList):
        if len(retList) == 0:
            return retList
        left = 0
        right = len(retList) - 1

        while left < right:
            tmp = retList[left]
            retList[left] = retList[right]
            retList[right] = tmp

            left += 1
            right -= 1

        return retList

    def reverseListByRecursion(self, retList):
        return retList

运行以上命令会出现以下错误

输入是: []
错误原因：没有在程序一开始就加上 corner case
修改位置：

class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []
        retList = []
        # ...