import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;
public class Main {
private static class TreeNode {
TreeNode left;
TreeNode right;
int data;
TreeNode(int newData) {
left = null;
right = null;
data = newData;
}
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int[] pre = new int[n];
for (int i = 0; i < n; i++)
pre[i] = input.nextInt();
int[] in = new int[n];
for (int i = 0; i < n; i++)
in[i] = input.nextInt();
input.close();
TreeNode treeNode = reConstructBinaryTree(pre, in);
prePost(treeNode);
}
public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre.length == 0 || in.length == 0)
return null;
TreeNode root = new TreeNode(pre[0]);
for (int i = 0; i < in.length; i++) {
if(in[i] == pre[0]){
//左子树,copyOfRange函数是左闭右开
root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
//递归构建左子树
root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
break;
}
}
return root;
}
public static void prePost(TreeNode root) {
if (root == null)
System.out.println("空树");
if (root.left != null)
prePost(root.left);
if (root.right != null)
prePost(root.right);
System.out.print(root.data + " ");
}
}
无法确定无法通过最后一个测试点的具体原因,但有几个常见的问题可能需要检查和排除:
程序逻辑问题:在对二叉树进行重构和遍历时,可能出现逻辑错误导致输出结果不符合预期。需要检查程序中的各个逻辑步骤,特别是递归过程中的操作是否正确。
内存问题:如果程序中使用了大量的内存,可能会导致程序在最后一个测试点出现超时或者内存溢出的情况。需要确保程序中的数据结构使用合理,避免内存占用过高。
边界问题:程序中可能存在一些特殊的输入数据,例如长度为0的数组、重复的数据等等,如果没有正确处理这些边界情况,就会导致程序在最后一个测试点出错。
建议在程序中加入一些调试输出,输出程序在执行时的一些中间状态,可以更容易地发现问题所在。同时,可以查看测试数据的具体情况,对照程序输出结果来分析问题