题目描述

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

输入描述:

2行,均为大写字母组成的字符串,表示一棵二叉树的中序与后序排列。

输出描述:

1行,表示一棵二叉树的先序。

示例1

输入
BADC
BDCA
输出
ABCD

解答

思路:
树的遍历方式:
先序遍历:先根节点后左右子树。
中序遍历:先左子树,再根节点,最后右子树。
后序遍历:先左右子树后根节点。

步骤:
先找到根节点并输出,即后序遍历的最后一点。
将中序遍历和后序遍历后的序列各分为两棵子树。
递归,重复一,二步骤,直到中序遍历后的长度小于等于0。

代码如下:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std; 
void tree(string s1,string s2){
	int len1=s1.size();	 
	int len2=s2.size();
	if(len1>0){	 
		char ch=s2[len2-1];	//根节点 
		cout<<ch;	//每次递归输出根节点 
		int pos=s1.find(ch);	//在s1中找到ch出现的位置 
		tree(s1.substr(0,pos),s2.substr(0,pos));	//递归左子树 
		tree(s1.substr(pos+1),s2.substr(pos,len1-pos-1));	//递归右子树 
	}
}
int main() {
	string str1,str2;
	cin>>str1>>str2;
	tree(str1,str2);	//构建左子树 
	return 0;
}

来源:RollerCompaction