LeetCode 102. 二叉树的层序遍历

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

102. 二叉树的层序遍历

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

题目

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

示例：

二叉树：[3,9,20,null,null,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

实现结果

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

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