Description
题目很简单，给你一棵二叉树的后序和中序序列，求出它的前序序列（So easy!）。
Input
输入有多组数据（少于100组），以文件结尾结束。
每组数据仅一行，包括两个字符串，中间用空格隔开，分别表示二叉树的后序和中序序列（字符串长度小于26，输入数据保证合法）。
Output
每组输出数据单独占一行，输出对应得先序序列。
Sample Input
ACBFGED ABCDEFGCDAB CBAD
Sample Output
DBACEGFBCAD
递归思路：
从后序序列中找根节点，找到后，遍历中序序列，以根节点为界将其分为左子树和右子树
打印根节点
递归左子树
递归右子树
实现步骤：
1.后序存入字符串数组a 中序存入字符串数组b
2.递归函数需要接收三个变量（1）根节点在a中的位置（2）b中所操作的部分的起始位置和结束位置
void recovery(int root,int start,int end)
3.进入函数后，遍历b，找到根节点位置，用i储存位置
4.打印根节点
5.递归左子树
ps：这里注意，此时递归要传的start和end和root是针对左子树ABC来说的
所以，root=toot-（end-i）-1； start不变； end=i-1；
6.递归右子树
同样的 针对EFG root=root-1； start=i+1；end不变；
注意：当end==start时，当前节点已经是叶子节点了，所以，start>end时，是递归结束条件。
代码：
#include<stdio.h>#include<string.h>void recovery(int root,int start,int end);char a[1000];char b[1000];int main(){while(scanf("%s",a)==1){scanf("%s",b);int l=strlen(a);recovery(l-1,0,l-1);printf("\n");}}void recovery(int root,int start,int end){if(start>end)return ;int i=start;//i用来遍历 while(i<end&&b[i]!=a[root])//遍历b 找到根节点 i++;printf("%c",a[root]);//打印根节点 recovery(root-(end-i)-1,start,i-1);//遍历左子树 recovery(root-1,i+1,end);//遍历右子树 }
如果觉得《已知二叉树的后序和中序遍历结果 求前序结果》对你有帮助，请点赞、收藏，并留下你的观点哦！
