【代码随想录day15】二叉树的层序遍历

最新推荐文章于 2025-01-28 00:25:56 发布

小小的香辛料

最新推荐文章于 2025-01-28 00:25:56 发布

阅读量115

点赞数

分类专栏：代码随想录数据结构 LeetCode 文章标签： leetcode 算法数据结构 python

本文链接：https://blog.csdn.net/doubleguy/article/details/131826221

版权

LeetCode 同时被 3 个专栏收录

112 篇文章

订阅专栏

数据结构

97 篇文章

订阅专栏

代码随想录

61 篇文章

订阅专栏

该文章介绍了一种使用队列进行二叉树层序遍历的方法，从根节点开始，逐层访问每个节点，确保同一层的节点按顺序输出。通过维护一个队列，每次遍历完一层的节点后将下一层的节点加入队列，直到队列为空。代码使用Python编写，返回每层节点值的列表。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目

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

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：

输入：root = [1]
输出：[[1]]
示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

思路

利用队列的先进先出的性质，存储每一层的节点。从跟节点开始，将当前节点弹出，并把当前节点的左右孩子放入队列中，这样一定能够保证是一层遍历完了才遍历下一层。这里我用count得到当前队列里的数量，把当前这一层的节点全部弹出，tmp存储每一层的节点结果，当这一层的结果都得到了再放到res中即可。

# 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: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        q = deque([root])
        res = []
        while q:
            count = len(q)
            tmp = []
            for _ in range(count):
                now = q.popleft()
                tmp.append(now.val)
                if now.left:
                    q.append(now.left)
                if now.right:
                    q.append(now.right)
            res.append(tmp)
        return res