POJ 2255:重建二叉树

http://bailian.openjudge.cn/practice/2255/

思路

在前序中找到根节点（每个前序串的第一个字符），然后在中序串中找到根节点的位置。前半部分是左子树，后半部分是右子树，递归输出。

#include <iostream> #include <cstdio> using namespace std; string front, middle; void print(int fs, int fl, int ms, int ml) // 当前前序子串开始下标、长度；当前中序子串开始下标、长度 { if(ml == 1) // middle只有一个 { cout<<middle[ms]; return; } if(ml == 0) // 没有这个子树，跳过 return; char root = front[fs]; // 根节点 int root_index = middle.find(root); // 在中序中的位置 print(fs+1, root_index-ms, ms, root_index-ms); print(fs+1+root_index-ms, ml-(root_index-ms)-1, root_index+1, ml-1-(root_index-ms)); cout<<root; } int main() { //freopen("in.txt", "r", stdin); while(cin>>front>>middle) { print(0, front.length(), 0, middle.length()); cout<<endl; } return 0; }