HDU 1710-Binary Tree Traversals（二进制重建）

Binary Tree Traversals

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3340 Accepted Submission(s): 1500

Problem Description

A binary tree is a finite set of vertices that is either empty or consists of a root r and two disjoint binary trees called the left and right subtrees. There are three most important ways in which the vertices of a binary tree can be systematically traversed or ordered. They are preorder, inorder and postorder. Let T be a binary tree with root r and subtrees T1,T2.

In a preorder traversal of the vertices of T, we visit the root r followed by visiting the vertices of T1 in preorder, then the vertices of T2 in preorder.

In an inorder traversal of the vertices of T, we visit the vertices of T1 in inorder, then the root r, followed by the vertices of T2 in inorder.

In a postorder traversal of the vertices of T, we visit the vertices of T1 in postorder, then the vertices of T2 in postorder and finally we visit r.

Now you are given the preorder sequence and inorder sequence of a certain binary tree. Try to find out its postorder sequence.

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.

Output

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

Sample Input

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

Sample Output

7 4 2 8 9 5 6 3 1
今天刷二叉树专题，搞了半天最终对重建有了一点认识，首先说一下由先序和中序重建二叉树，大体思路是大概是这种：由于先序（pre）的第一个字母肯定是根节点。所以要在中序（ins）序列中找到根节点的位置k，然后递归重建根节点的左子树和右子树。此时要把左子树和右子树当成根节点，然后表示出它们的位置，左子树非常好说，pre+1就是它的位置。对于右子树来说，pre+k+1为它的位置。如图

对于由中序和后序重建，思路跟上面大体一样，详细写法有点区别。这个就要在中序序列中找到后序的最后一个字母（即根节点），然后递归重建左子树和右子树，依然是把左子树和右子树当成根节点。左子树的位置为pos+k-1，但传的參数应该是pos   （由于我们要找的字母是pos[n-1]）,而右子树的位置在后序的倒数第二个字母。传參数为pos+k。（不是pos+k+1，想明确这个就算真明确了）

另为这篇没写由后序和中序重建的代码，曾经写过，在这点击打开链接
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <list>
using namespace std;
const int INF=1<<27;
const int maxn=5100;
typedef struct node
{
	int data;
	node *l,*r;
}*T;
void rbuild(T &root,int *pre,int *ins,int n)
{
  if(n<=0)
	root=NULL;
  else
  {
  	root=new node;
  	int k=find(ins,ins+n,pre[0])-ins;
	root->data=pre[0];
	rbuild(root->l,pre+1,ins,k);
	rbuild(root->r,pre+k+1,ins+k+1,n-k-1);
  }
}
int ans[maxn],p;
void last(T root)
{
	if(root)
	{
		last(root->l);
		last(root->r);
		ans[p++]=root->data;
	}
}
int main()
{
	int n,i;
	while(cin>>n){
	T root;int pre[maxn],ins[maxn];
	for(i=0;i<n;i++)
		cin>>pre[i];
	for(i=0;i<n;i++)
		cin>>ins[i];
	rbuild(root,pre,ins,n);
	p=0;
	last(root);
	for(i=0;i<p;i++)
		if(i!=p-1)
		cout<<ans[i]<<" ";
	    else
		cout<<ans[i]<<endl;
	}
	return 0;
}