根据二叉树的前中遍历求层次遍历java

### 构造二叉树并通过层次遍历输出 要实现通过前序和中序遍历构建二叉树并完成层次遍历的功能，可以按照以下方法设计 Java 程序。 #### 前提条件 - **前序遍历**的顺序为 `根 -> 左子树 -> 右子树`[^2]。 - **中序遍历**的顺序为 `左子树 -> 根 -> 右子树`[^3]。 - 利用前序遍历的第一个元素作为当前子树的根节点，并从中序遍历中找到该根的位置，从而划分左右子树[^1]。 #### 实现逻辑 以下是完整的 Java 代码示例： ```java import java.util.LinkedList; import java.util.Queue; class TreeNode { int val; TreeNode left, right; TreeNode(int x) { val = x; } } public class BinaryTreeConstruction { public static TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder.length == 0 || inorder.length == 0) return null; // 创建哈希表存储中序遍历中的索引位置以便快速查找 return helper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1); } private static TreeNode helper(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) { if (preStart > preEnd || inStart > inEnd) return null; // 当前子树的根节点 TreeNode root = new TreeNode(preorder[preStart]); // 找到根节点在中序遍历中的位置 int inIndex = 0; for (int i = inStart; i <= inEnd; i++) { if (inorder[i] == root.val) { inIndex = i; break; } } // 计算左子树长度 int leftSize = inIndex - inStart; // 递归构造左子树和右子树 root.left = helper(preorder, preStart + 1, preStart + leftSize, inorder, inStart, inIndex - 1); root.right = helper(preorder, preStart + leftSize + 1, preEnd, inorder, inIndex + 1, inEnd); return root; } public static void levelOrderTraversal(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); if (root != null) queue.add(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); System.out.print(node.val + " "); if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } } public static void main(String[] args) { int[] preorder = {0, 1, 3, 7, 8, 4, 2, 5, 6}; int[] inorder = {7, 3, 8, 1, 4, 0, 5, 2, 6}; TreeNode root = buildTree(preorder, inorder); levelOrderTraversal(root); // 输出应为: 0 1 2 3 4 5 6 7 8 } } ``` #### 解析 1. 使用递归函数 `helper` 来逐步构建二叉树。每次递归调用都会处理一个子树范围内的数据。 2. 在 `levelOrderTraversal` 方法中，利用队列来逐层访问二叉树的所有节点[^4]。 3. 主程序中定义了测试用的前序和中序数组，并验证最终的结果是否匹配预期的层次遍历序列。 ---