根据先序和中序输出后序遍历
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/weixin_42449444/article/details/86178278
题目描述：
二叉树的前序、中序、后序遍历的定义： 前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树； 中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树； 后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。 给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。
输入描述:
两个字符串，其长度n均小于等于26。
第一行为前序遍历，第二行为中序遍历。
二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。输出描述:
输入样例可能有多组，对于每组测试样例，
输出一行，为后序遍历的字符串。输入样例：
ABC
BAC
FDXEAG
XDEFAG输出样例：
BCA
XEDGAF相关知识：
1.先序遍历的递归过程为：若二叉树为空，遍历结束。否则：①访问根结点；②先序遍历根结点的左子树；③先序遍历根结点的右子树。 简单来说先序遍历就是在深入时遇到结点就访问。
2.中序遍历的递归过程为：若二叉树为空，遍历结束。否则：①中序遍历根结点的左子树；②访问根结点；③中序遍历根结点的右子树。简单来说中序遍历就是从左子树返回时遇到结点就访问。
3.后序遍历的递归过程为：若二叉树为空，遍历结束。否则：①后序遍历根结点的左子树；②后序遍历根结点的右子树；③访问根结点。简单来说后序遍历就是从右子树返回时遇到结点就访问。
AC代码：
#include <bits/stdc++.h>
using namespace std;
void getpost(string preorder,string inorder) //根据先序和中序求后序
{
int n = preorder.length(); //n为每次遍历数目
if(n > 0)
{
char root = preorder[0]; //根结点为先序遍历的第一个
int i = inorder.find(root); //中序遍历中根结点的所在下标
getpost(preorder.substr(1,i),inorder.substr(0,i)); //左子树
getpost(preorder.substr(i+1),inorder.substr(i+1)); //右子树
cout << root;
}
}
int main()
{
string preorder,inorder; //先序遍历和中序遍历
while(cin >> preorder >> inorder)
{
getpost(preorder,inorder);
cout << endl;
}
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-01-09 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录