二叉树的层序遍历算法详解

# 1. 介绍

在本章节中，我们将介绍二叉树的层序遍历算法。我们将会讨论什么是二叉树，什么是层序遍历算法，以及为什么层序遍历算法在二叉树中有重要的应用。让我们一起来深入探讨！

# 2. 实现层序遍历算法的基本思路

层序遍历算法通过逐层访问节点的方式，按照从上到下、从左到右的顺序遍历二叉树，是一种广度优先搜索（BFS）的应用。在对二叉树进行层序遍历时，我们通常采用队列的数据结构来辅助实现。以下将详细介绍如何实现层序遍历算法的基本思路。

# 3. 二叉树的层序遍历实现方法

层序遍历是一种常见且重要的二叉树遍历方式，在实际应用中有着广泛的使用。接下来将介绍二叉树层序遍历的具体实现方法，包括递归实现和迭代实现，并给出示例代码演示。

#### 3.1 递归实现

二叉树的层序遍历可以通过递归实现，在递归过程中需要传入当前节点和当前层次，将节点按照层次加入到对应的列表中，最终得到按层次遍历的结果。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def level_order_recursive(root, level, result):
    if not root:
        return
    if len(result) < level + 1:
        result.append([])
    result[level].append(root.val)
    level_order_recursive(root.left, level + 1, result)
    level_order_recursive(root.right, level + 1, result)

# 示例代码
# 创建一个二叉树
#        3
#       / \
#      9  20
#         / \
#        15  7
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

result_recursive = []
level_order_recursive(root, 0, result_recursive)
print(result_recursive)  # 输出 [[3], [9, 20], [15, 7]]

在上述示例代码中，使用递归实现了二叉树的层序遍历，通过传入当前节点、当前层次和结果列表来实现按层次存储节点，最终得到层序遍历的结果。

#### 3.2 迭代实现

除了递归的方法，我们还可以通过迭代的方式来实现二叉树的层序遍历。借助队列结构