POJ 2255 Tree Recovery（还原树）

题目链接：POJ 2255

题意：

给出二叉树的前序和中序遍历求出后序遍历。

分析：

递归。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <fstream>
#include <algorithm>
using namespace std;struct TreeNode {struct TreeNode* left;struct TreeNode* right;char elem;
};void BinaryTreeFromOrderings(char* inorder, char* preorder, int length)
{if (length == 0) return;TreeNode* node = new TreeNode;node->elem = *preorder;int rootIndex = 0;for (;rootIndex < length;rootIndex++)if (inorder[rootIndex] == *preorder) break;BinaryTreeFromOrderings(inorder, preorder + 1, rootIndex);BinaryTreeFromOrderings(inorder + rootIndex + 1, preorder + rootIndex + 1, length - (rootIndex + 1));cout << node->elem;return;
}
int main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifchar in[27], pre[27];int len;while (cin >> pre >> in){len = strlen(pre);BinaryTreeFromOrderings(in, pre, len);cout << endl;}return 0;
}