PTA 树的遍历 java_java pta 树的遍历

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;
	
}