题目描述：

描述 Description

给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示，长度≤8)。

输入格式 Input Format

第一行为二叉树的中序序列

第二行为二叉树的后序序列

输出格式 Output Format

一行，为二叉树的先序序列

样例输入 Sample Input

BADC BDCA

样例输出 Sample Output

ABCD

#include 
  
   
#include 
   
     using namespace std; struct bitree { char data; bitree *lchild, *rchild; }; string inorder, postorder, ltree_inorder, rtree_inorder, ltree_postder, rtree_postder; int index1, index2; char rtree_first; void preorder(bitree *&root, string inorder, string postder, int lm, int rm, int lp, int rp) { root = new bitree; root->data = postorder[rp]; root->lchild = root->rchild = NULL; int pos = lm; while (inorder[pos] != postder[rp]) { pos++; } int lenl = pos - lm; //左树的长度 if (pos > lm) { preorder(root->lchild, inorder, postorder, lm, pos - 1, lp, lp + lenl - 1); } if (pos < rm) { preorder(root->rchild, inorder, postorder, pos + 1, rm, lp + lenl, rp - 1); } } void Preorder(bitree *&root) { if (root){ cout << root->data; Preorder(root->lchild); Preorder(root->rchild); } } int main() { bitree *root; cin >> inorder >> postorder; preorder(root, inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1); Preorder(root); system("pause"); }