二叉树遍历（已知先序、中序求后序）

柔情只为你懂 2022-06-09 10:30 174阅读 0赞

### 【例3-4】求后序遍历 ###

时间限制: 1000 ms 内存限制: 65536 KB  
提交数: 11 通过数: 9

### 【题目描述】 ###

输入一棵二叉树的先序和中序遍历序列，输出其后序遍历序列。

### 【输入】 ###

共两行，第一行一个字符串，表示树的先序遍历，第二行一个字符串，表示树的中序遍历。树的结点一律用小写字母表示。

### 【输出】 ###

一行，表示树的后序遍历序列。

### 【输入样例】 ###

abdec
    dbeac

### 【输出样例】 ###

debca

### 【来源】 ###

[No][]

[提交 ][Link 1][统计信息][Link 2]

![20170903230717841][]

代码：

#include<iostream>
    #include<cstring>
    using namespace std;
    string s1,s2;
    void calc(int l1,int r1,int l2,int r2)
    {
    	int m=s2.find(s1[l1]);//找到根节点在中序遍历中的位置 
    	if(m>l2) calc(l1+1,m-l2+l1,l2,m-1);//遍历左子树 
    	if(m<r2) calc(m-l2+l1+1,r1,m+1,r2);//遍历右子树 
    	cout<<s1[l1];//输出根节点 
    }
    int main()
    {
    	cin>>s1>>s2;
    	calc(0,s1.length()-1,0,s2.length()-1);
    	cout<<endl;
    	return 0;
    }

[No]: http://ybt.ssoier.cn:8088/problem_search.php?searchsource=No
[Link 1]: http://ybt.ssoier.cn:8088/submit.php?pid=1339
[Link 2]: http://ybt.ssoier.cn:8088/problem_stat.php?pid=1339
[20170903230717841]: /images/20220609/56bd127ae9994f72b98dbfec85dfa17d.png

发表评论取消回复

表情：

评论列表（有 0 条评论，174人围观）

还没有评论，来说两句吧...

相关阅读

相关二叉树的遍历（前序、中序、后序、已知前中序求后序、已知中后序求前序）

![9ae3b38d3e56c024e830ca7a9395315b.png][] 之前的一篇随笔（[二叉树、前序遍历、中序遍历、后序遍历][Link 1]）只对二叉树的

秒速五厘米/ 2022年12月19日 00:53/ 0 赞/ 138 阅读

相关二叉树系列（二）：已知中序遍历序列和后序遍历序列，求先序遍历序列

前面已经介绍过三种遍历方法的规则，为了大家看着方便，这里我们在重新介绍一遍： 1.先序遍历 (1)访问根结点； (2)先序遍历左子树； (3)先序遍历

悠悠/ 2022年08月13日 00:38/ 0 赞/ 119 阅读

相关二叉树系列（一）：已知先序遍历序列和中序遍历序列，求后序遍历序列

首先介绍一下三种遍历顺序的操作方法： 1.先序遍历 (1)访问根结点； (2)先序遍历左子树； (3)先序遍历右子树。 2.中序遍历

今天药忘吃喽~/ 2022年08月13日 00:38/ 0 赞/ 130 阅读

相关已知二叉树先序遍历中序遍历求其后序遍历、重建二叉树

已知二叉树先序遍历中序遍历求其后序遍历 (注：已知中序遍历序列和剩下两种遍历序列中的一种都可以确定二叉树，即可得到另一种遍历序列，但是已知前序遍历和后

水深无声/ 2022年08月09日 01:53/ 0 赞/ 147 阅读

相关二叉树遍历（已知中序、先序求后序）

二叉树的遍历 Time Limit: 1000ms Memory Limit: 32768KB This problem will be judged on HRBU

灰太狼/ 2022年06月09日 10:38/ 0 赞/ 167 阅读

相关二叉树遍历（已知先序、中序求后序）

【例3-4】求后序遍历时间限制: 1000 ms 内存限制: 65536 KB 提交数: 11 通过数: 9 【题目描述】输入一棵二叉树的先

柔情只为你懂/ 2022年06月09日 10:30/ 0 赞/ 175 阅读

相关先序创建二叉树及先序、中序、后序遍历

先序二叉树 //先序建立二叉树 void createBiTree(BiTree &T){ int cnt; scanf("%d",&cn

短命女/ 2022年05月27日 09:09/ 0 赞/ 143 阅读

相关 (模板)已知二叉树先序(后序)中序,求这棵二叉树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsZXgx

柔情只为你懂/ 2022年04月23日 01:04/ 0 赞/ 137 阅读

相关二叉树(先序遍历，中序遍历，后序遍历)

二叉树定义每个节点的子节点数(度)不能大于2 先序遍历定义：从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。

悠悠/ 2021年10月01日 09:18/ 0 赞/ 423 阅读

相关树之二叉树遍历先序，中序，后序

一、介绍 ![这里写图片描述][20160905190552651] 二、遍历理解 ![这里写图片描述][20160905190704230] 三、先序算法

青旅半醒/ 2021年09月11日 01:46/ 0 赞/ 530 阅读