做网站怎么报价,中国互联网协会,浏览器下载,零基础学做网站有一棵二叉树#xff0c;每个节点由一个大写字母标识(最多26个节点#xff09;。
现有两组字母#xff0c;分别表示后序遍历#xff08;左孩子-右孩子-父节点#xff09;和中序遍历#xff08;左孩子-父节点-右孩子#xff09;的结果#xff0c;请你输…
有一棵二叉树每个节点由一个大写字母标识(最多26个节点。
现有两组字母分别表示后序遍历左孩子-右孩子-父节点和中序遍历左孩子-父节点-右孩子的结果请你输出层序遍历的结果。
输入
每个输入文件一行第一个字符串表示后序遍历结果第二个字符串表示中序遍历结果。每串只包含大写字母
中间用单空格分隔。
输出
输出仅一行表示层序遍历的结果结尾换行。
样例输入
CBEFDA CBAEDF
样例输出
ABDCEF
代码带有详细解释
package Date3Point21;import java.util.*;/*** 有一棵二叉树每个节点由一个大写字母标识(最多26个节点。* 现有两组字母分别表示后序遍历左孩子-右孩子-父节点和中序遍历左孩子-父节点-右孩子的结果请你输出层序遍历的结果。*/
public class MainE {private static String result;//设置全局结果的返回public static void main(String[] args) {Scanner scannernew Scanner(System.in);String s1 scanner.next();//后序String s2 scanner.next();//中序String[] split1 s1.split();//切割String[] split2 s2.split();MapInteger,String nomalSortnew HashMap();//用map集合来存储每个节点在数组中的位置以及节点值myfunction(split1,split2,nomalSort,0);//从中序序列和后续序列得到完全二叉树的数组形式key对应在数组中的位置value对应该节点的值bianli(nomalSort,0);//得到map集合存储的完全二叉树的数组形式进行层次遍历得到结果System.out.println(result);}/*** 层次遍历* param nomalSort* param i 起始节点*/private static void bianli(MapInteger, String nomalSort, int i) {QueueInteger stacknew LinkedList();//用队列来实现层次遍历stack.add(i);while (!stack.isEmpty()){Integer pop stack.poll();resultnomalSort.get(pop);if(nomalSort.containsKey(pop*21)){stack.add(pop*21);}if(nomalSort.containsKey(pop*22)){stack.add(pop*22);}}}/**** param split1 后序* param split2 中序* param nomalSort 正常* param index 正常顺序中的数组索引*/private static void myfunction(String[] split1, String[] split2, MapInteger,String nomalSort, int index) {if(split1.length0 || split2.length0){//如果中序或者后序数组的大小为0说明该子树为空。return;}if(split1.length1){//如果中序或者后序数组的大小为1直接可以赋值而无需做其他操作。nomalSort.put(index,split1[0]);return;}nomalSort.put(index,split1[split1.length-1]);//将父节点加入map集合String parentsplit1[split1.length-1];//得到后序序列的最后一个结点最后一个节点就是该部分的最顶层的节点for(int i0;isplit2.length;i){//循环遍历中序序列得到根结点所在位置然后即可找到左右子树if(split2[i].equals(parent)){String[] inLeft Arrays.copyOfRange(split2, 0, i);//中序遍历的左子树String[] inRight Arrays.copyOfRange(split2, i1, split2.length);//中序遍历中的右子树String[] postLeft Arrays.copyOfRange(split1, 0, i);//后序遍历中的左子树String[] postRight Arrays.copyOfRange(split1, i, split1.length-1);//后序遍历中的右子树myfunction(postLeft,inLeft,nomalSort,index*21);//递归进入下一层左孩子结点myfunction(postRight,inRight,nomalSort,index*22);//递归进入下一层右孩子结点break;}}}
}
