层次遍历算法详解：二叉树与多叉树的遍历方法 | 代码实现与应用场景

层次遍历（Level Order Traversal）是一种常见的树或图的遍历算法，通常用于二叉树或多叉树。它按照树的层次从上到下、从左到右依次访问每个节点。层次遍历通常使用队列（Queue）数据结构来实现。

层次遍历的基本思路：

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

代码实现（JavaScript）：

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

function levelOrderTraversal(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 currentNode = queue.shift();
            currentLevel.push(currentNode.val);

            if (currentNode.left) {
                queue.push(currentNode.left);
            }
            if (currentNode.right) {
                queue.push(currentNode.right);
            }
        }

        result.push(currentLevel);
    }

    return result;
}

// 示例用法
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);

console.log(levelOrderTraversal(root));
// 输出: [[1], [2, 3], [4, 5, 6, 7]]

解释：

• queue 用于存储当前层的节点。
• result 用于存储每一层的节点值。
• 每次循环处理一层节点，并将下一层的节点加入队列。

时间复杂度：

• 每个节点都会被访问一次，因此时间复杂度为 O(n)，其中 n 是树中节点的数量。

空间复杂度：

• 最坏情况下，队列中会存储树的一层节点，因此空间复杂度为 O(w)，其中 w 是树的最大宽度（即最宽层的节点数）。

应用场景：

• 层次遍历常用于需要按层处理树结构的场景，如二叉树的序列化、反序列化、打印树的结构等。

扩展：

• 如果需要区分每一层的节点，可以在遍历时记录当前层的节点数（如代码中的 levelSize），这样可以方便地处理每一层的节点。

希望这个解释和代码示例对你有帮助！如果你有更多问题，欢迎继续提问。