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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int[] preorder = new int[N];
        int[] inorder = new int[N];
        for (int i = 0; i < N; i++) {
            preorder[i] = input.nextInt();
        }
        for (int i = 0; i < N; i++) {
            inorder[i] = input.nextInt();
        }
        new Main().buildTree(preorder, inorder);
    }
    Map<Integer, Integer> map = new HashMap<>();
    int[] preorder;
    public void buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        build(0, preorder.length-1, 0, inorder.length-1);
    }
    private void build(int preStart, int preEnd, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) {
            return ;
        }
        int rootVal = preorder[preStart];
        int rootIndex = map.get(rootVal);
        int leftNum = rootIndex - inStart;
        build(preStart+1, preStart+leftNum, inStart, rootIndex-1);
        build(preStart+leftNum+1, preEnd, rootIndex+1, inEnd);
        System.out.print(rootVal + " ");
    }
}

import java.util.*;
public class Main { 
public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = Integer.parseInt(scanner.nextLine());
        List<String> pre = Arrays.asList(scanner.nextLine().split(" "));
        List<String> order = Arrays.asList(scanner.nextLine().split(" "));
        List<String> post = new ArrayList<>();
        coverTree(pre, order, post);
        for (String s : post) {
            System.out.print(s+" ");
        }
    }

    private static void coverTree(List<String> pre, List<String> order, List<String> post) {
        if (pre.isEmpty() || order.isEmpty()) {
            return;
        }
        post.add(0, pre.get(0));
        int location = order.indexOf(pre.get(0));
        coverTree(pre.subList(location + 1, pre.size()), order.subList(location + 1, order.size()), post);
        coverTree(pre.subList(1, location + 1), order.subList(0, location), post);
    }
}

#include<bits/stdc++.h>
using namespace std;
// 无需建树，直接利用树的性质即可，递归解决
void getPost(vector<int>& pre,vector<int>& in,int pre_s,int pre_e,int in_s,int in_e,vector<int>& ans)
{
    if(pre_s>pre_e) return;
    int root = pre[pre_s];
    int index;
    for(index = in_s;index<=in_e;++index)
        if(in[index]==root)
            break;
   //   根节点
    ans.push_back(root);
    // 处理右子树
    getPost(pre,in,pre_s+(index-in_s)+1,pre_e,index+1,in_e,ans);
    // 处理左子树
    getPost(pre,in,pre_s+1,pre_s+index-in_s,in_s,index-1,ans);

}
int main()
{
    int n;
    cin>>n;
    vector<int>ans;
    vector<int>pre(n);
    vector<int>in(n);

    for(int i=0;i<n;++i)
        cin>>pre[i];
    for(int i=0;i<n;++i)
        cin>>in[i];
    getPost(pre,in,0,n-1,0,n-1,ans);
    for(int i=ans.size()-1;i!=-1;i--)
        cout<<ans[i]<<" ";

    return 0;
}

import java.util.ArrayList;
import java.util.Scanner;

public class Main {


    /**
     * res: 存放后续遍历的结果
     */
    public static ArrayList<Integer> res = new ArrayList<>();


    /**
     * 树的结点定义
     */
    public static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node(int val, Node left, Node right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 根据先序和中序建树
     * @param pre 先序遍历数组
     * @param in 后序遍历数组
     * @param preL 先序子树左边界
     * @param preR 先序子树右边界
     * @param inL 中序子树左边界
     * @param inR 中序子树有边界
     * @return 子树根节点，最后一次回溯是树的根节点
     */
    public static Node create(int[] pre, int[] in, int preL, int preR, int inL, int inR) {
        if (preL > preR) {
            return null;
        }
        Node node = new Node(pre[preL], null, null);
        // 根据先序和中序确定左右子树的根节点在中序遍历的位置
        int mid;
        for (mid = inL; pre[preL] != in[mid]; mid++);
        // 构建左子树
        node.left = create(pre, in, preL+1, preL+mid-inL, inL, mid-1);
        // 构建右子树
        node.right = create(pre, in, preL+mid-inL+1, preR, mid+1, inR);
        return node;
    }

    // 后序遍历
    public static void postOrder(Node node) {
        if (node != null) {
            postOrder(node.left);
            postOrder(node.right);
            res.add(node.val);
        }
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int[] pre = new int[N];
        int[] in = new int[N];
        for (int i = 0; i < N; i++) {
            pre[i] = input.nextInt();
        }
        for (int i = 0; i < N; i++) {
            in[i] = input.nextInt();
        }
        Node node = create(pre, in, 0, N-1, 0, N-1);
        postOrder(node);
        for (int i = 0; i < res.size(); i++) {
            System.out.print(res.get(i));
            if (i != res.size()-1) {
                System.out.print(" ");
            }
        }
    }
}

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

#建立后序遍历序列
def getLast(pre, mid):
    #如果只有一个节点
    #直接返回
    if len(pre) <= 1:
        return pre
    #先序遍历的第一个节点是根节点
    root = pre[0]
    #划分左右子树
    index = mid.index(root)
    preLeft = pre[1:index + 1]
    preRight = pre[index + 1:]
    midLeft = mid[:index]
    midRight = mid[index + 1:]
    #后序遍历的顺序是左右根
    return getLast(preLeft, midLeft) + getLast(preRight, midRight) + [root]

if __name__ == '__main__':
    #读入数据
    n = int(input())
    pre = input()
    pre = pre.split()
    mid = input()
    mid = mid.split()
    #建立后序遍历序列
    last = getLast(pre, mid)
    print(' '.join(last))

#include <stdio.h>
#include <stdlib.h>

typedef struct {
  int val;
  int l_child, r_child;
} TreeNodeInfo, *INFO;

TreeNodeInfo infos[10010]; // 全局区

int createTree(int* pre, int* inorder, int i, int j, int n) {
  // recursion exit condition
  if (n <= 0) return 0;
  if (n == 1) return *(pre + i);

  int k = j;
  while (*(inorder + k) != *(pre + i)) ++k;
  int l = k - j;
  
  infos[*(pre + i)].l_child = createTree(pre, inorder, i + 1, j, l);
  infos[*(pre + i)].r_child = createTree(pre, inorder, i + 1 + l, k + 1, n - 1 - l);
  return *(pre + i);
}

void postorder(INFO infos, int index) {
  if (!index) return;
  postorder(infos, infos[index].l_child);
  postorder(infos, infos[index].r_child);
  fprintf(stdout, "%d ", index);
}

int main(int argc, char* argv[]) {
  int n;
  fscanf(stdin, "%d", &n);
  
  int i, pre[n], inorder[n];
  for (i = 0; i < n; ++i) fscanf(stdin, "%d", pre + i);
  for (i = 0; i < n; ++i) fscanf(stdin, "%d", inorder + i);
  
  createTree(pre, inorder, 0, 0, n);
  postorder(infos, *pre);
  return 0;
}

import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;

public class Main {
    private static int posIndex;
    private static Map<Integer, Integer> map = null;
    private static int[] pos = null;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        map = new HashMap<>();
        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 i = 0; i < n; i++) {
            in[i] = sc.nextInt();
            map.put(in[i], i);
        }
        pos = new int[n];
        posIndex = n - 1;
        process(pre, 0, n - 1, in, 0, n - 1);
        for (int i = 0; i < n; i++) {
            if (i != 0) {
                System.out.print(" ");
            }
            System.out.print(pos[i]);
        }
    }

    public static void process(int[] pre, int preL, int preR, int[] in, int inL, int inR) {
        if (preL > preR || inL > inR) {
            return;
        }
        int root = pre[preL];
        pos[posIndex--] = root;
        int k = map.get(root);
        int leftSize = k - inL, rightSize = inR - k;
        process(pre, preL + leftSize + 1, preR, in, k + 1, inR);
        process(pre, preL + 1, preL + leftSize, in, inL, k - 1);
    }
}

利用的是根据前序和中序还原树的思路求解的该问题，从右向左还原后序遍历数组

def setPos(preorder, inorder, posorder, si):
    if len(inorder)==0&nbs***bsp;si < 0:
        return si
    data = preorder[0]
    mid = inorder.index(data)
    posorder[si] = data
    si = si-1
    si = setPos(preorder[mid+1:], inorder[mid+1:], posorder, si)
    si = setPos(preorder[1:mid+1], inorder[0:mid], posorder, si)
    return si

n = int(input())
prorder = list(map(int, input().split()))
inorder = list(map(int, input().split()))

posorder = n*['']
s = setPos(prorder, inorder, posorder, n-1)
for i in range(n):
    print(posorder[i], end=' ')

n=int(input())
preOrder=list(map(int,input().split()))
inOrder=list(map(int,input().split()))

def postOrder(preOrder,inOrder):
    if len(preOrder)==1&nbs***bsp;len(preOrder)==0:
        return preOrder
    ind=inOrder.index(preOrder[0])
    left=postOrder(preOrder[1:1+ind],inOrder[:ind])
    right=postOrder(preOrder[1+ind:],inOrder[ind+1:])
    return left+right+[preOrder[0]]
po=postOrder(preOrder,inOrder)
print(' '.join(map(str,po)))

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

}