题意：

用栈的形式给出一棵树建立的顺序，要求输出后序遍历

思路：

push的顺序就是先序遍历，pop出的顺序就是中序遍历，所以直接用二叉树先序和中序遍历转后序即可。主要记录一下模板

#include
    
     #define inf 0x3f3f3f3fusing namespace std;const int maxn = 10000;vector
     
       inOrder,preOrder,postOrder;stack
      
        tree;/*先序中序转后序*/void post(int root, int left, int right) {	if (left > right) return;	int i = left;	while (i < right&&inOrder[i] != preOrder[root]) i++;	post(root+1, left, i - 1);	post(root+1+i-left, i + 1, right);	postOrder.push_back(preOrder[root]);}int main() {	int n;	scanf("%d", &n);	string s;	int num;	while(inOrder.size()
       
        > s;		if (s[1] == 'u') {			scanf("%d", &num);			tree.push(num);			preOrder.push_back(num);		} else {			int temp = tree.top();			tree.pop();			inOrder.push_back(temp);		}	}	post(0, 0, n - 1);	for (int i = 0; i < n; i++) {		if (i == 0) {			printf("%d",postOrder[i]);		} else {			printf(" %d",postOrder[i]);		}	}	return 0;}
       
      
     
    

后序中序求先序：

#include 
    
     using namespace std;int post[] = {3, 4, 2, 6, 5, 1};int in[] = {3, 2, 4, 1, 6, 5};void pre(int root, int start, int end) {    if(start > end) return ;    int i = start;    while(i < end && in[i] != post[root]) i++;    printf("%d ", post[root]);    pre(root - 1 - end + i, start, i - 1);    pre(root - 1, i + 1, end);}int main() {    pre(5, 0, 5);    return 0;}