SWUST OJ#983 利用中序和后序遍历求先序遍历

目录

题目

思路

代码

题目

题目描述

已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历，但已知先序和后序，却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及后序遍历结果，要求输出其先序遍历结果。

输入

第一行为中序序列 第二行为后续序列

输出

输出为遍历二叉树得到的先序序列 

样例输入

BFDAEGC
FDBGECA

样例输出

ABDFCEG

思路

首先先要把三种遍历弄明白

前序遍历：★根->左孩子->右孩子

中序遍历：左孩子->★根->右孩子

后序遍历：左孩子->右孩子->★根

关键突破点就是遍历时根节点的位置

根据定义，后序遍历的最后一个节点即是根节点。

找到根节点，再确定根节点在中序序列中的位置，就可以分出左右两棵子树。

然后再在已知的左右子树中，故技重施，再次按照上述步骤，再次

找到左右孩子的根节点，再确定左右孩子的根节点在中序序列中的位置，就可以再次分出左右两棵子树。

下面假设某棵树的中序遍历：CBEDFAHG。后序遍历：CEFDBHGA。

分界线标准：

中序：已经判断根节点的左右两边以 | 分开。左边是左子树，右边是右子树。

后序：左右子树以 | 分开。左边是左子树，右边是右子树。zho

[ ]表示当前搜索的区间

红色表示当前步骤的判断，蓝色表示已经搜过的节点。

(注意想明白分界线 | 和 [] ，这对之后代码的理解有极大帮助）

第①步：

中序：[CBEDF | A | HG]  后序：[CEFDB | HG A]

可知：第一层就是A，也就是根节点，同时可以得知 A的左孩子(左子树)的元素有：BCDEF，右孩子(右子树)的元素有：GH 。

第②步：

中序：[C | B | EDF]A[HG]  后序：[C | EFD B][H G] A

可知：第二层是B和G。也就是左右孩子的根节点，同时可以得知 B的左孩子(左子树)的元素只有C，右孩子(右子树)的元素有：DEF。G的左孩子(左子树)只有H，且不存在右孩子。

第③步：

中序：[C]B[E | D | F]A[H]G  后序：[C][E | F D] B [H] GA

可知：第三层是C，D和H。并且C和H是叶子节点，同时可以得知 D的左孩子是E，右孩子是F。

第④步：

中序：CB[E]D[F]AHG  后序：C [E][F] DBHGA

可知：第四层是E和F，并且他们都是叶子节点。

所以根据以上分析，按照每一步的步骤，已经可以画出这棵树了

​               A/ \B　　G/ \　/C  D H/ \E   F

然而说了这么多，题目是要求我们求出前续遍历呀，但我们只是有能力求出这棵树。

由于暴力建树确实过于复杂，所以直接深搜

//建树
string ord,post;
//so,eo表示搜索ord,也就是搜索中序遍历每一个元素
//so表示从前往后搜,eo表示从后往前搜
//sp,ep表示搜索post,也就是搜索后序遍历每一个元素
//sp表示从前往后搜,ep表示从后往前搜
void dfs(int so,int eo,int sp,int ep) {if(so>eo||sp>ep) return;for(int i=so,j=sp;i<=eo;i++,j++) {if(ord[i]==post[ep]) { //找到相同了,那么他就是根节点cout<

#include 
#include 
#include 
#include 
using namespace std;
string ord,post;
void dfs(int so,int eo,int sp,int ep) {if(so>eo||sp>ep) return;for(int i=so,j=sp;i<=eo;i++,j++) {if(ord[i]==post[ep]) {cout<>ord>>post;dfs(0,ord.size()-1,0,post.size()-1);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！