二叉树的层序遍历

本文详细讲解了 LeetCode 102 题“二叉树的层序遍历”，提供了 DFS 和 BFS 两种解法，并附有完整的 Python 代码实现。

Leetcode 二叉树 BFS DFS Python

阅读要点

层序遍历的两种实现：DFS 和 BFS
DFS 使用递归和哈希表记录层级
BFS 使用队列逐层遍历
两种解法的时间复杂度均为 O(n)

题目

102. 二叉树的层序遍历 - 力扣（LeetCode）

解法一：DFS（深度优先搜索）

思路

深度优先搜索（DFS）是一种递归遍历树的方法。在层序遍历中，我们可以在递归时记录每个节点的层级，并将节点值放入对应层级的列表中。

具体步骤如下：

使用一个字典 mp，键为层级，值为该层节点值的列表。
从根节点开始递归，递归时传入当前节点和层级。
如果节点为空，直接返回。
将节点值添加到 mp[level] 中。
递归处理左子树和右子树，层级加 1。
递归结束后，按层级顺序将字典中的列表取出，组成最终结果。

代码

# 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]]:
        
        self.mp = collections.defaultdict(list)
        def dfs(node, level):
            if not node:
                return 
            self.mp[level].append(node.val)
            dfs(node.left, level + 1)
            dfs(node.right, level + 1)
        dfs(root, 0)
        res = []
        for k in self.mp:
            res.append(self.mp[k])
        return res

解法二：BFS（广度优先搜索）

思路

广度优先搜索（BFS）是层序遍历最直观的方法。我们使用队列，逐层处理节点。

具体步骤如下：

如果根节点为空，直接返回空列表。
初始化一个队列，将根节点入队。
当队列不为空时，记录当前队列的长度 q_size，这个长度就是当前层的节点数。
循环 q_size 次，每次从队列中取出一个节点，将其值加入当前层的结果列表 level_res，并将其左右子节点（如果存在）加入队列。
将 level_res 加入最终结果 res。
队列为空时，遍历结束，返回 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 []
        res = []
        q = deque([root])
 
        while q:
            q_size = len(q)
            level_res = []
            for _ in range(q_size):
                node = q.popleft()
                level_res.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(level_res)
        return res

总结

层序遍历是二叉树遍历的重要方法，BFS 和 DFS 各有优劣。BFS 直观且易于理解，DFS 则更节省空间（在树不平衡时）。掌握这两种方法有助于解决更多树相关问题。