• binary 二进制
• finite 有限的
• vertices 根节点

struct node{
	int value;
	node *left,*right;
	node(int value=0,node *left=NULL,node *right=NULL):value(value),left(left),right(right){};	
};

先序遍历（preorder）

中左右：1 2 4 7 3 5 8 9 6

void preoder(node *root){
	if(root!=NULL){//判断是否到底 
		cout<<root->value;//输出这个根的值 
		preorder(root->left);//递归左子树 
		preorder(root->right);//递归右子树 
	}
}

中序遍历（inorder）

左中右：4 7 2 1 8 5 9 3 6

void inorder(node *root){
	if(root!=NULL){
		inorder(root->left);
		cout<<root->value;
		inorder(root->right); 
	}
}

后序遍历（postorder）

左右中：7 4 2 8 9 5 6 3 1

void postorder(node *root){
	if(root!=NULL){
		postorder(root->left);
		postorder(root->right);
		cout<<root->value;
	}
}

例

Binary Tree Traversals

已知先序遍历和中序遍历，求后序遍历

Input

The input contains several test cases. The first line of each test case contains a single integer n (1<=n<=1000), the number of vertices of the binary tree. Followed by two lines, respectively indicating the preorder sequence and inorder sequence. You can assume they are always correspond to a exclusive binary tree.

9
1 2 4 7 3 5 8 9 6
4 7 2 1 8 5 9 3 6

Output

For each test case print a single line specifying the corresponding postorder sequence.

7 4 2 8 9 5 6 3 1

#include<cstdio>
#include<iostream>
using namespace std;
const int N=1010;

int k,pre[N],in[N],post[N];//k记录节点数 
struct node{
	int value;
	node *left,*right;
	node(int value=0,node *left=NULL,node *right=NULL):value(value),left(left),right(right){};
};
void buildtree(int left,int right,int &t,node *&root){
	int flag=-1;//查找根节点位置
	for(int i=left;i<=right;i++){
		if(in[i]==pre[t]){//根据先序和中序遍历找根节点的位置 
			flag=i;//把根节点位置存入 flag 
			break;
		}
	}
	if(flag==-1) return;//如果没有根节点就返回 
	root=new node(in[flag]);//创建一个叶子用 root 指向 
	t++;//层数加 1 
	if(flag>left) buildtree(left,flag-1,t,root->left);//继续找当前节点的左指数 
	if(flag<right) buildtree(flag+1,right,t,root->right);//继续找当前节点的右指数 
} 
void postorder(node *root){
	if(root!=NULL){
		postorder(root->left);//遍历左子树 
		postorder(root->right);//遍历右子树 
		post[k++]=root->value;//存入当前节点的值 
	}
} 
void remove_tree(node *root){
	if(root==NULL) return;
	remove_tree(root->left);
	remove_tree(root->right);
	delete root;
}
int main(void){
	int n;
	while(~scanf("%d",&n)){//cin可能会超时 
		for(int i=1;i<=n;i++) scanf("%d",&pre[i]);
		for(int i=1;i<=n;i++) scanf("%d",&in[i]);
		node *root;//创建一个无指向的结点指针 
		int t=1;//表示树的层数 
		buildtree(1,n,t,root);//构建树 1表示左指数,n表示右指数 
		k=0;//后根序列的下标 
		postorder(root);//存储后根序列 
		for(int i=0;i<k;i++) printf("%d%c",post[i],i==k-1?'\n':' ');//输出 
		remove_tree(root);//清空树 
	}
	return 0;
}