PTA 树的遍历题目https://pintia.cn/problem-sets/1120858298571182080/problems/1120858728923549696
参考博客:https://blog.csdn.net/wenbo201/article/details/76572981
思路:
核心是建树过程
每一次先由后序序列找到根节点的大小,每一次递归函数传入的后序序列的最后一个数,就是这次的根节点的大小
然后找出这个数在中序序列中的位置;
然后递归建立左右子树
package pat树;
//ac
//参考博客
//https://blog.csdn.net/wenbo201/article/details/76572981
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main56树的遍历 {
static int n;
static int []po;
static int []id;
static Queue<node>q=new LinkedList<node>();
//核心是建树过程
//每一次先由后序序列找到根节点的大小,每一次递归函数传入的后序序列的最后一个数,就是这次的根节点的大小
//然后找出这个数在中序序列中的位置;
//然后递归建立左右子树
public static node build(int pl,int pr,int il,int ir) {
if(il>ir)return null;
node root=new node();
//每一次先由后序序列找到根节点的大小,每一次递归函数传入的后序序列的最后一个数,就是这次的根节点的大小
int v=po[pr];
root.v=v;
int i;
//然后找出这个数在中序序列中的位置;
for(i=il;i<=ir;i++)if(id[i]==v)break;
int num=i-il;
//然后递归建立左右子树
root.le=build(pl,pl+num-1,il,i-1);
root.ri=build(pl+num,pr-1,i+1,ir);
return root;
}
public static void print() {
int t=1;
while(!q.isEmpty()) {
node r=q.poll();
if(t==n)System.out.println(r.v);
else {
System.out.print(r.v+" ");
t++;
}
if(r.le!=null)q.add(r.le);
if(r.ri!=null)q.add(r.ri);
}
}
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
n=in.nextInt();
po=new int[n+1];
id=new int[n+1];
for(int i=1;i<=n;i++)po[i]=in.nextInt();
for(int i=1;i<=n;i++)id[i]=in.nextInt();
node root=build(1,n,1,n);
q.add(root);
print();
}
}
class node{
int v;
node le;
node ri;
}