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

UVa 548：Tree 二叉树的重建——中序遍历与后续遍历进行建树2014-10-06 csdn博客 shuangde800题目链接：

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 63 1 2 5 6 7 47 8 11 3 5 16 12 188 3 11 7 16 18 12 5255255

样例输出：

分析：

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

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

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

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

// 由中序和后序遍历序列进行建树， 返回根结点指针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;} // 由前序和中序遍历序列进行建树， 返回根结点的指针// 本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45532.htmNode * 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（）！="
"） 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
",pResult[minPos]->data）;}return 0;}