102. 二叉树的层序遍历

Difficulty

Medium

法一：宽度优先搜索 (迭代)

思路：

在简单层次遍历的基础上，增加一个变量用来记录每一层的节点个数

解答：


class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        result = []
        if root is None:
            return result
        queue = []
        queue.append(root)
        while len(queue) > 0:
            temp_len = len(queue) # 记录当前层有几个节点
            temp_list = [] # 存放当前层的节点
            while temp_len > 0:
                temp_node = queue.pop(0)
                temp_list.append(temp_node.val)
                if temp_node.left is not None:
                    queue.append(temp_node.left)
                if temp_node.right is not None:
                    queue.append(temp_node.right)
                temp_len -= 1
            result.append(temp_list) # 将当前层节点列表 放到result中
        return result

法二：深度优先搜索(回溯)

思路

先序遍历二叉树，遍历的时候采用辅助变量depth来记录当前层数，然后如果层数大于等于result中的数组数，就向result中添加一个空数组，然后将当前节点值加到result[depth]中

💡

注意：本体采用了隐式的回溯法，所以没有撤销选择这一步

题解


# 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]]:
        res = []
        self.preOrder(node=root, depth=0, result=res)
        return res

    def preOrder(self, node, depth, result):
        if node is None:
            return None
        # 如果当前层 >= result 中的数组个数,说明开始了新的一层,需要新添加一个空数组
        if depth >= len(result):
            result.append([])
        result[depth].append(node.val)
        self.preOrder(node.left, depth+1, result)
        self.preOrder(node.right, depth+1, result)