本文主要是介绍【Tsinghua】树重建(Rebuild)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题就是各种顺序的遍历一棵树。。。
树重建(Rebuild)
描述
某二叉树的n个节点已经用[1, n]内的整数进行了编号。现给定该二叉树的中序遍历序列和后序遍历序列，试输出其对应的先序遍历序列。
输入
第一行为一个整数n。
第二、三行，即已知的中序、后序遍历序列。
输出
仅一行。
若所给的中序、后序遍历序列的确对应于某棵二叉树，则输出其先序遍历序列。否则，输出-1。
输入样例1
5
4 2 5 1 3
4 5 2 3 1
输出样例1
1 2 4 5 3输入样例2
3
2 3 1
1 2 3
输出样例2
-1限制
1 ≤ n ≤ 5000
时间：2 sec
空间：256MB
输入和输出的遍历序列均为[1, n]内整数的一个排列，整数间均以空格分隔，行末没有多余空格。
提示
不同遍历序列中根节点的位置。
AC的代码：
#include <stdio.h>
#include <stdlib.h>
#define MAXN 5005int in[MAXN]; //中序
int af[MAXN]; //后序
int ans[MAXN]; //最后输出的前序序列
int count=0;struct TreeNode
{struct TreeNode* left;struct TreeNode* right;int elem;
};TreeNode* BinTree(int inorder[], int aftorder[], int length)
{if(length == 0){return NULL;}TreeNode* node = new TreeNode; //新建一个树节点node->elem = *(aftorder+length-1);ans[count++]=node->elem; //存入答案int rootIndex=0;for( ;rootIndex<length;rootIndex++) //在中序遍历中找这个根节点{if(inorder[rootIndex]==*(aftorder+length-1))break;}if(rootIndex>=length){printf("-1\n");exit(0);}node->left = BinTree(inorder,aftorder,rootIndex);node->right = BinTree(inorder+rootIndex+1 , aftorder+rootIndex , length-(rootIndex+1));return node;
}int main()
{int n;scanf("%d",&n);int i;for(i=0;i<n;i++)scanf("%d",&in[i]);for(i=0;i<n;i++)scanf("%d",&af[i]);BinTree(in,af,n);for(i=0;i<count-1;i++)printf("%d ",ans[i]);printf("%d\n",ans[i]);return 0;
}
这篇关于【Tsinghua】树重建(Rebuild)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
