LeetCode 102. 二叉树的层序遍历 | Python

时间：2021-05-28 19:56:45

102. 二叉树的层序遍历

题目来源：https://leetcode-cn.com/problems/binary-tree-level-order-traversal

题目

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：

二叉树：[3,9,20,null,null,15,7],

    3

   / \

  9  20

    /  \

   15   7

返回其层次遍历结果：

[

  [3],

  [9,20],

  [15,7]

]

解题思路

思路：广度优先搜索

本题，我们使用广度优先搜索的思路来解决。

广度优先搜索（BFS），它是按照层进行搜索的。题目中要求，按层序遍历得到所需的节点。那么这里就跟 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 []

        # 返回结果

        res = []

        from collections import deque

        # 定义队列

        queue = deque()

        # 将根节点入队

        queue.append(root)

        # 队列不为空，表达式二叉树还有节点，循环遍历

        while queue:

            # 先标记每层的节点数

            size = len(queue)

            # 定义变量，记录每层节点值

            level = []

            # 这里开始遍历当前层的节点

            for _ in range(size):

                # 出队

                node = queue.popleft()

                # 先将当前节点的值存储

                level.append(node.val)

                # 节点的左右节点非空时，入队

                if node.left is not None:

                    queue.append(node.left)

                if node.right is not None:

                    queue.append(node.right)

            # 添加每层的节点值列表

            res.append(level)

        return res

实现结果

LeetCode 102. 二叉树的层序遍历 | Python

以上就是使用广度优先搜索，借助队列先入先出的性质，逐层遍历，得到所需求的解，进而解决《102. 二叉树的层序遍历》问题的主要内容。

欢迎关注微信公众号《书所集录》

相关文章