1.题目描述
一个二叉树，树中每个节点的权值互不相同。
现在给出它的后序遍历和中序遍历，请你输出它的层序遍历。
输入格式
第一行包含整数 N，表示二叉树的节点数。
第二行包含 N个整数，表示二叉树的后序遍历。
第三行包含 N 个整数，表示二叉树的中序遍历。
输出格式
输出一行 N 个整数，表示二叉树的层序遍历。
数据范围
1≤N≤30,
官方并未给出各节点权值的取值范围，为方便起见，在本网站范围取为 1∼N。
输入样例：
72 3 1 5 7 6 41 2 3 4 5 6 7
输出样例：
4 1 6 3 5 7 2
2.思路分析
后序遍历根节点在最后一个，前序遍历根节点是第一个，根据根节点位置在中序遍历中可以区分出左右子树，据此来重建二叉树。
本题难点在于递归建树时，中序和后序遍历的区间选择，举例如下图：
3.Ac代码
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.HashMap; import java.util.Queue; public class Main { static int N=40; //后序遍历，中序遍历 static int []postorder=new int[N]; static int []inorder=new int[N]; static HashMap<Integer,Integer> idx=new HashMap<>(); //存储中序遍历的下标 static HashMap<Integer,Integer> l=new HashMap<>(); static HashMap<Integer,Integer> r=new HashMap<>(); public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); int n=Integer.parseInt(br.readLine()); String []s=br.readLine().split(" "); for (int i = 0; i < n; i++) postorder[i]=Integer.parseInt(s[i]); s=br.readLine().split(" "); for (int i = 0; i < n; i++) { inorder[i]=Integer.parseInt(s[i]); idx.put(inorder[i],i ); } int root=bulide(0,n-1,0,n-1); //构建二叉树 bfs(root); } private static void bfs(int t) { //BFS用来层序遍历输出 Queue<Integer> que=new ArrayDeque<>(); que.add(t); while (!que.isEmpty()){ int root=que.poll(); System.out.print(root+" "); if(l.containsKey(root)) que.add(l.get(root)); //判断该节点的左右儿子是否存在 if(r.containsKey(root)) que.add(r.get(root)); //存在则加入队列，等待下一层遍历 } } private static Integer bulide(int il, int ir, int pl, int pr) { int root=postorder[pr]; //根节点是后序遍历的最后一个 int k=idx.get(root); //获取根节点在中序遍历中的下标 if(il<k) //如果中序遍历有节点小于根节点，那么存在左子树 //下面两行是难点，举例解释见图 l.put(root,bulide(il,k-1,pl,pl+k-1-il)); if(ir>k) //如果中序遍历有节点大于根节点，那么存在右子树 r.put(root,bulide(k+1,ir,pl+k-il,pr-1)); return root; } }
感谢你能看完， 如有错误欢迎评论指正，有好的思路可以交流一波，如果对你有帮助的话，点个赞支持下
