UVa 548 - Tree 二叉树的重建——中序遍历与后续遍历进行建树

548-Tree

4606

28.96%

974

77.21%

题目链接：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=489

题目类型： 数据结构， 二叉树

题目大意：

给两个组数字，都是在同一棵二叉树上的，第一组是按中序遍历（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

分析：

这题就是运用了二叉树重建， 以及遍历。

二叉树的遍历：先序遍历，中序遍历，后序遍历
只要有一个中序序列再加上另一个序列就可唯一地重建原来二叉树。

进行了二叉树重建之后，只要对这棵二叉树进行搜索， 取得各个路径之和，然后找出最小的那个和即可。

由中序遍历 分别和前序遍历，后序遍历进行建树的方法：

// 由中序和后序遍历序列进行建树， 返回根结点指针
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代码：

#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;
}

—— 生命的意义，在于赋予它意义。

原创http://blog.csdn.net/shuangde800，By D_Double