L2-3 完全二叉树的层序遍历（Java）

### Java 实现完全二叉树的层序遍历 为了实现完全二叉树的层序遍历，可以基于题目描述中的性质以及后序遍历的结果来构建一棵完整的二叉树结构。以下是具体的解决方案： #### 方法概述 1. **输入处理**：读取后序遍历序列作为输入数据。 2. **编号映射**：通过递归的方式将后序遍历结果映射到对应的节点位置上[^4]。 3. **层序输出**：按照完全二叉树的特性，依次打印每一层的节点。 下面是一个详细的 Java 实现方案： ```java import java.util.Scanner; public class CompleteBinaryTreeLevelOrder { static int[] tree; static int index = 0; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 输入结点数量 N int n = scanner.nextInt(); tree = new int[n + 1]; // 存储后序遍历序列 int[] postOrder = new int[n]; for (int i = 0; i < n; i++) { postOrder[i] = scanner.nextInt(); } // 构建完全二叉树并填充数值 buildTree(postOrder, 1, n); // 层序遍历输出 for (int i = 1; i <= n; i++) { System.out.print(tree[i]); if (i != n) { System.out.print(" "); } } scanner.close(); } private static void buildTree(int[] postOrder, int rootIndex, int size) { if (rootIndex > size) return; // 左子树递归 buildTree(postOrder, rootIndex * 2, size); // 右子树递归 buildTree(postOrder, rootIndex * 2 + 1, size); // 填充当前节点值 tree[rootIndex] = postOrder[index++]; } } ``` --- #### 关键逻辑解析 1. **数组存储完全二叉树** 使用 `tree` 数组模拟完全二叉树的存储方式，索引从 `1` 开始表示根节点的位置。根据完全二叉树的定义： - 节点 `i` 的左孩子位于 `2*i`； - 节点 `i` 的右孩子位于 `2*i + 1`； 2. **递归构造树** 后序遍历的特点决定了最后一个访问的节点是根节点。因此可以通过递归来先填充值给叶子节点，再逐步向上返回至父节点。 3. **层序遍历输出** 完全二叉树的层序遍历可以直接按顺序输出数组中的元素（忽略未使用的部分）。这种方式的时间复杂度为 O(N)，非常高效。 --- #### 测试案例分析 以下是对测试用例的具体验证过程： ##### 输入样例 ``` 8 91 71 2 34 10 15 55 18 ``` ##### 处理流程 - 将后序遍历 `[91, 71, 2, 34, 10, 15, 55, 18]` 映射到完全二叉树中。 - 结果如下表所示： | 索引 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |------|----|----|----|----|----|----|----|----| | 值 | 18 | 34 | 55 | 71 | 2 | 10 | 15 | 91 | ##### 输出样例 ``` 18 34 55 71 2 10 15 91 ``` --- ### 注意事项 1. 输入的数据应严格满足完全二叉树的要求，即后序遍历能够唯一确定一颗完全二叉树[^1]。 2. 如果输入规模较大（接近上限），需注意内存分配和性能优化。 ---