二叉树的广度优先遍历方法（BFS）

我来为你详细介绍二叉树广度优先遍历的循环实现方法。

二叉树节点定义

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

1. 基本层序遍历

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

2. 分层的层序遍历

function levelOrderByLevels(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;
}

12. 完整测试示例

// 构建测试二叉树
//       3
//      / \
//     9   20
//    /   /  \
//   8   15   7
 
const root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.left.left = new TreeNode(8);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
 
console.log('基本层序遍历:', levelOrder(root));
// 输出: [3, 9, 20, 8, 15, 7]
 
console.log('分层层序遍历:', levelOrderByLevels(root));
// 输出: [[3], [9, 20], [8, 15, 7]]
 

13. 核心要点总结

BFS循环实现的关键技巧：

1. 队列管理：使用 shift() 出队，push() 入队
2. 层级控制：记录当前层的节点数量 levelSize
3. 状态跟踪：根据需要添加额外信息（如位置、层级等）
4. 结果处理：根据具体需求处理每层的结果

时间和空间复杂度：

• 时间复杂度：O(n)，其中 n 是节点数量
• 空间复杂度：O(w)，其中 w 是树的最大宽度

BFS的循环实现简洁高效，是处理二叉树层序遍历问题的首选方法。