UVa 548 - Tree 二叉树的重建——中序遍历与后续遍历进行建树
题目大意:
给两个组数字,都是在同一棵二叉树上的,第一组是按中序遍历(inorder)顺序输出的,第二组是按后序遍历(postorder)输出的, 根据这两组数据构建出原来的二叉树,然后计算从根结点到每个叶子结点的路径上的数字之和, 输出最小之和。
样例输入:
3 2 1 4 5 7 6
3 1 2 5 6 7 4
7 8 11 3 5 16 12 18
8 3 11 7 16 18 12 5
255
255
样例输出:
1
3
255
分析:
这题就是运用了二叉树重建, 以及遍历。
二叉树的遍历:先序遍历,中序遍历,后序遍历
只要有一个中序序列再加上另一个序列就可唯一地重建原来二叉树。
进行了二叉树重建之后,只要对这棵二叉树进行搜索, 取得各个路径之和,然后找出最小的那个和即可。
由中序遍历 分别和前序遍历,后序遍历进行建树的方法:
[cpp]
// 由中序和后序遍历序列进行建树, 返回根结点指针
Node * InPostCreateTree(int *mid,int *post,int len){
if(len == 0)
return NULL;
int i=len-1;
while(post[len-1] != mid[i])
--i;
Node *h=NewNode();
h->data=post[len-1];
h->left=InPostCreateTree(mid,post,i);
h->right=InPostCreateTree(mid+i+1,post+i,len-i-1);
return h;
}
// 由前序和中序遍历序列进行建树, 返回根结点的指针
Node * PreInCreateTree(int *mid,int *pre,int len) //n标识s2的长度
{
if(len==0)
return NULL;
int i = 0;
while(*mid != pre[i])
++i;
Node *h=NewNode();
h->data= *mid;
h->left = PreInCreateTree(mid+1, pre, i);
h->right = PreInCreateTree(mid+i+1, pre+i+1, len-i-1);
return h;
}
AC代码:
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int MAXN = 10005;
int inOrder[MAXN], postOrder[MAXN], nIndex;
class Node{
public:
int data;
Node *left;
Node *right;
};
int nodeIndex;
Node node[MAXN];
vector<int>result;
vector<Node*>pResult;
bool flag;
int ans;
inline Node* NewNode(){
node[nodeIndex].left = NULL;
node[nodeIndex].right = NULL;
return &node[nodeIndex++];
}
inline void input(){
nIndex=1;
while(getchar()!='\n')
scanf("%d", &inOrder[nIndex++]);
// 输入第二行,后序遍历
for(int i=0; i<nIndex; ++i)
scanf("%d", &postOrder[i]);
}
// 由中序和后序遍历序列进行建树, 返回根结点指针
Node * InPostCreateTree(int *mid,int *post,int len){
if(len == 0)
return NULL;
int i=len-1;
while(post[len-1] != mid[i])
--i;
Node *h=NewNode();
h->data=post[len-1];
h->left=InPostCreateTree(mid,post,i);
h->right=InPostCreateTree(mid+i+1,post+i,len-i-1);
return h;
}
void dfs(Node *root, int n){
if(!root->left && !root->right){
result.push_back(n+root->data);
pResult.push_back(root);
return ;
}
if(root->left) dfs(root->left, n+root->data);
if(root->right) dfs(root->right, n+root->data);
}
int main(){
freopen("input.txt","r",stdin);
while(~scanf("%d", &inOrder[0])){
input();
nodeIndex = 0;
Node *root = InPostCreateTree(inOrder, postOrder, nIndex);
result.clear();
pResult.clear();
dfs(root, 0);
int minPos = 0;
for(int i=1; i<result.size(); ++i)
if(result[i] < result[minPos]) minPos=i;
printf("%d\n",pResult[minPos]->data);
}
return 0;
}
作者:shuangde800
补充:软件开发 , C++ ,