本文共 2279 字，大约阅读时间需要 7 分钟。

4606

28.96%

974

77.21%

题目链接：

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

题目大意：

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

样例输出：

13255

分析：

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

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

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

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

// 由中序和后序遍历序列进行建树， 返回根结点指针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
   
    #include
    
     #include
     
      #include
      
       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
       
        result;vector
        
         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
         
          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
          
           data); } return 0;}
          
         
        
       
      
     
    
   

转载地址：http://muzni.baihongyu.com/