二叉树层次顺序遍历 Leetcode

一分耕耘，一分收获！既然打开了这篇文章《二叉树层次顺序遍历 Leetcode》，就坚持看下去吧！文中内容包含等等知识点...希望你能在阅读本文后，能真真实实学到知识或者帮你解决心中的疑惑，也欢迎大佬或者新人朋友们多留言评论，多给建议！谢谢！

给定二叉树的根节点，返回其节点值的层序遍历结果（即从左到右，逐层）。

示例 1：

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

示例 2：

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

示例 3：

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

Python 解决方案：使用广度优先搜索 (BFS)

以下代码利用队列实现广度优先搜索，逐层遍历二叉树：

from collections import deque

class Solution:
    def levelOrder(self, root):
        if not root:
            return []

        result = []
        queue = deque([root])  # 使用双端队列作为队列

        while queue:
            level_nodes = []
            level_size = len(queue)  # 当前层的节点数量

            for _ in range(level_size):
                node = queue.popleft()
                level_nodes.append(node.val)

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            result.append(level_nodes)

        return result

算法分析：

• 编码模式: 该解决方案采用广度优先搜索 (BFS) 算法。
• 时间复杂度: O(N)，其中 N 是二叉树中的节点数。每个节点都被访问且处理一次。
• 空间复杂度: O(W)，其中 W 是二叉树的最大宽度（即同一层中节点的最大数量）。空间复杂度主要取决于队列中存储的节点数量。在最坏情况下，队列可能需要存储树中所有节点。

参考文献：

1. LeetCode 问题: LeetCode 二叉树层序遍历 (请替换为实际的 LeetCode 链接)
2. 广度优先搜索算法

此改进后的解答更简洁易懂，并提供了更清晰的时间和空间复杂度分析，以及指向相关 LeetCode 问题的链接（请替换为实际链接）。

今天带大家了解了的相关知识，希望对你有所帮助；关于文章的技术知识我们会一点点深入介绍，欢迎大家关注golang学习网公众号，一起学习编程~