[其他目] 由中根序列和后根序列重建二叉树＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2013-11-09 20:23:03| 人2,844| 回0 | 上一篇 | 下一篇

[其他目] 由中根序列和后根序列重建二叉树

推 0 收藏 0 0 站台

前序走
定中序走、後序走

描述

我们知道如何按照三种深度优先次序来周游一棵二叉树，来得到中根序列、前根序列和后根序列。反过来，如果给定二叉树的中根序列和后根序列，或者给定中根序列和前根序列，可以重建一二叉树。本题输入一棵二叉树的中根序列和后根序列，要求在内存中重建二叉树，最后输出这棵二叉树的前根序列。

用不同的整数来唯一标识二叉树的每一个结点，下面的二叉树

中根序列是9 5 32 67

后根序列9 32 67 5

前根序列5 9 67 32

输入

两行。第一行是二叉树的中根序列，第二行是后根序列。每个数字表示的结点之间用空格隔开。结点数字范围0～65535。暂不必考虑不合理的输入数据。

输出

一行。由输入中的中根序列和后根序列重建的二叉树的前根序列。每个数字表示的结点之间用空格隔开。

样例输入

9 5 32 67 9 32 67 5

样例输出

5 9 67 32

之前有到一，一下。

#include <stdio.h>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
int parseInt(int a[], char s[]) {
   int n = 0;
   stringstream sin(s);
   while(sin >> a[n])
       n++;
   return n;
}
int Idx, cidx = 0;
int a[1024], b[1024], c[1024];
void dfs(int l, int r) {
   if(l > r)
       return;
   int i, j = l;
   for(i = l; i <= r; i++) {
       if(a[i] == b[Idx]) {
           j = i;
           break;
       }
   }
   Idx--;
   dfs(j+1, r);
   dfs(l, j-1);
   c[cidx++] = a[j];
}
int main() {
   char s[1024];
   int i, j, k, n;
   while(gets(s)) {
       n = parseInt(a, s);
       gets(s);
       n = parseInt(b, s);
       Idx = n-1, cidx = 0;
       dfs(0, n-1);
       for(i = cidx-1; i >= 0; i--) {
           if(i != cidx-1)
               putchar(' ');
           printf("%d", c[i]);
       }
       puts("");
   }
   return 0;
}