通过先序和中序数组生成后序数组

import java.util.*;
 
public class Main {
    int index = 0;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] pre = new int[n];
        int[] in = new int[n];
        int[] end = new int[n];
        //map存储中序遍历中各结点对应的索引
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0; i<n; i++)
            pre[i] = scanner.nextInt();
        for(int i=0; i<n; i++){
            in[i] = scanner.nextInt();
            map.put(in[i], i);
        }
        //先将根结点放到最末尾，因为递归遍历左右子树完成后会把根节点返回
        //故在此先将根节点放到正确位置
        end[n-1] = pre[0];
        //递归遍历左右子树
        new Main().endOrder(pre, 0, n-1, in, 0, n-1, end, map);
        //打印后序遍历结果
        for(int x : end)
            System.out.print(x+" ");
    }
    public int endOrder(int[] pre, int preStart, int preEnd, 
                        int[] in, int inStart, int inEnd,
                        int[] end, Map<Integer,Integer> map){
        if(preStart > preEnd)
            return 0;
        //节点只有1个直接返回
        if(preStart == preEnd)
            return pre[preStart];
        //获取前序遍历开始点在中序遍历中的索引
        int k = map.get(pre[preStart]);
        //左子树长度
        int length = k - inStart;
        //递归遍历左子树
        int left = endOrder(pre, preStart+1, preStart+length, in, inStart, k-1, end, map);
        //left不为空即左子树不为空
        if(left != 0)
            end[index++] = left;
        //递归遍历右子树
        int right = endOrder(pre, preStart+length+1, preEnd, in, k+1, inEnd, end, map);
        //right不为空即右子树不为空
        if(right != 0)
            end[index++] = right;
        //遍历结束左右子树后返回根节点
        return pre[preStart];
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] pre = new int[n];
        int[] in = new int[n];
        for (int i = 0; i < n; i++) {
            pre[i] = sc.nextInt();
        }
        for (int j = 0; j < n; j++) {
            in[j] = sc.nextInt();
        }
        
        int[] res = findPos(pre, in);
        for(int i = 0; i < res.length; i++) {
            System.out.print(res[i] + " ");
        }
    }
    
    //无需一定生成二叉树，只分析数组亦可
    //根据当前的先序和中序数组，设置pos arr中最右边空白位置的数，然后划分
    //出左子树的先序、中序数组，以及右子树的先中序数组。
    //先根据右子树的划分设置好后序数组，再根据左子树的划分，从右往左一次设置pos arr。
    public static int[] findPos(int[] pre, int[] in) {
        if (pre == null || in == null)
            return null;
        int len = pre.length;
        int[] pos = new int[len];
        process(pre, in, 0, len-1, 0, len-1, pos, len-1);
        return pos;
    }
    
    public static int process (int[] pre, int[] in, int preS, 
                                int preE, int inS, int inE, 
                                int[] pos, int index) {
        if (preS > preE)
            return index;
        pos[index--] = pre[preS];
        int mid;
        for(mid = inS; in[mid] != pre[preS]; mid++);
        index = process(pre, in, preS+mid-inS+1, preE, mid+1, inE, pos, index);
        return process(pre, in, preS+1, preS+mid-inS, inS, mid-1, pos, index);
    }
}

import java.util.*;

public class Main {
	static int[] preArr;
	static int[] inArr;
	static int[] arr;
	static Map<Integer, Integer> map;
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
        preArr = new int[n];
        inArr = new int[n];
        for(int i=0;i<n;i++){
        	preArr[i] = scanner.nextInt();
        }
         map = new HashMap<Integer, Integer>();
        for(int i=0;i<n;i++){
        	inArr[i] = scanner.nextInt();
        	map.put(inArr[i], i);
        }
        arr = new int[n];
        setArr(0, n-1, 0, n-1, n-1);
        for(int i=0;i<n;i++) {
        	System.out.print(arr[i]+" ");
        }
	}
	
	static  int setArr(int preStart,int preEnd,int inStart,int inEnd,int postIndex) {
		if(preStart>preEnd) return postIndex;
		
		arr[postIndex--] = preArr[preStart];
		int index = map.get(preArr[preStart]);
		
		postIndex = setArr(index - inStart + preStart +1 , preEnd, index+1,inEnd,postIndex);
		return setArr(preStart+1,index - inStart + preStart ,inStart,index-1 ,postIndex);
	}

}