二叉树的层序遍历实现

定义与原理

层序遍历（Level Order Traversal）是二叉树遍历的一种方式，按照从上到下、从左到右的顺序逐层访问树中的所有节点。这种遍历方式也称为广度优先搜索（Breadth-First Search, BFS）。

层序遍历的核心思想是使用队列（Queue）数据结构来辅助实现，通过队列的先进先出（FIFO）特性保证节点按照层级顺序被访问。

实现方法

基本算法步骤

1. 将根节点放入队列
2. 当队列不为空时，执行以下操作：
   • 取出队首节点并访问
   • 将该节点的左子节点（如果存在）加入队列
   • 将该节点的右子节点（如果存在）加入队列
3. 重复步骤2，直到队列为空

分层存储的层序遍历

如果需要将每一层的节点分开存储（例如返回一个二维数组，其中每个子数组代表一层），可以在上述算法基础上增加一个记录当前层节点数的步骤：

1. 将根节点放入队列
2. 当队列不为空时：
   • 记录当前队列大小（即当前层的节点数）
   • 创建一个临时数组存储当前层的节点值
   • 循环处理当前层的所有节点：
     • 取出队首节点，将其值加入临时数组
     • 将其左右子节点加入队列
   • 将临时数组加入结果数组
3. 返回结果数组

代码实现

Python实现

from collections import deque

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

def levelOrder(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
                
        result.append(current_level)
    
    return result

JavaScript实现

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function levelOrder(root) {
    if (!root) return [];
    
    const result = [];
    const queue = [root];
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel = [];
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            currentLevel.push(node.val);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        result.push(currentLevel);
    }
    
    return result;
}

Java实现

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new ArrayList<>();
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);
                
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            
            result.add(currentLevel);
        }
        
        return result;
    }
}

可视化表示

层序遍历过程

二叉树层序遍历示例

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树中的节点数。我们需要访问每个节点一次。
• 空间复杂度：O(w)，其中 w 是二叉树的最大宽度（即最多节点的层的节点数）。在最坏情况下，当树是完全平衡时，最后一层包含大约 n/2 个节点，所以空间复杂度为 O(n)。

变体问题

自底向上的层序遍历

将层序遍历的结果反转即可实现自底向上的遍历。

def levelOrderBottom(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
                
        result.append(current_level)
    
    return result[::-1]  # 反转结果

锯齿形层序遍历

奇数层从左到右，偶数层从右到左的遍历方式。

def zigzagLevelOrder(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    left_to_right = True
    
    while queue:
        level_size = len(queue)
        current_level = [0] * level_size
        
        for i in range(level_size):
            node = queue.popleft()
            # 根据方向确定插入位置
            index = i if left_to_right else level_size - 1 - i
            current_level[index] = node.val
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
                
        result.append(current_level)
        left_to_right = not left_to_right
    
    return result

参考资源

• LeetCode 102. 二叉树的层序遍历: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
• GeeksforGeeks - Binary Tree Level Order Traversal: https://www.geeksforgeeks.org/level-order-tree-traversal/
• 算法图解 - 层序遍历: https://github.com/azl397985856/leetcode/blob/master/problems/102.binary-tree-level-order-traversal.md