102. 二叉树的层序遍历

· 逐层遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        all_floor = [[root]]

        this_floor = [root]
        while this_floor:
            next_floor = []
            # print(this_floor)
            for i in this_floor:
                if i:
                    if i.left != None:
                        next_floor.append(i.left)
                    if i.right != None:
                        next_floor.append(i.right)
            if next_floor:
                all_floor.append(next_floor)
            this_floor = next_floor
        
        all_floor_val = []
        for i in all_floor:
            this_floor_val = []
            for j in i:
                if j:
                    this_floor_val.append(j.val)
            if this_floor_val:
                all_floor_val.append(this_floor_val)
        
        return all_floor_val

· 递归法

注意顺序先左后右

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []
        
        result = []
        
        def add_to_result(level, node):
            """
            递归函数
            :param level int 当前在二叉树的层次
            :param node TreeNode 当前节点
            """
            if level > len(result) - 1:
                result.append([])
                
            result[level].append(node.val)
            if node.left:
                add_to_result(level+1, node.left)
            if node.right:
                add_to_result(level+1, node.right)
        
        add_to_result(0, root)
        return result

· BFS

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []  # 特殊情况，root为空直接返回
        from collections import deque
        # 下面就是BFS模板内容，BFS关键在于队列的使用
        layer = deque()
        layer.append(root)  # 压入初始节点
        res = []  # 结果集
        while layer:
            cur_layer = []  # 临时变量，记录当前层的节点
            for _ in range(len(layer)):  # 遍历某一层的节点
                node = layer.popleft()  # 将要处理的节点弹出
                cur_layer.append(node.val)
                if node.left:  # 如果当前节点有左右节点，则压入队列，根据题意注意压入顺序，先左后右，
                    layer.append(node.left)
                if node.right:
                    layer.append(node.right)
            res.append(cur_layer)  # 某一层的节点都处理完之后，将当前层的结果压入结果集
        return res

· DFS

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res = []
        self.level(root, 0, res)
        return res

    def level(self, root, level, res):
        if not root: return
        if len(res) == level: res.append([])
        res[level].append(root.val)
        if root.left: self.level(root.left, level + 1, res)
        if root.right: self.level(root.right, level + 1, res)