首页 > 代码库 > 二叉树的有趣问题
二叉树的有趣问题
近期看了一下hihocoder,那里面有一个很有趣的题目,就是给出二叉树的前序遍历结果,然后给出中续遍历的结果,最后求出后续遍历的结果,我觉得这个题目很有趣,然后刚好那里有提示,先给出一个图吧
那么这个图的前序遍历(TLR)结果是
ABDEGHCFIJ
中续遍历(LTR)结果是
DBGEHACIJF
后续遍历(LRT)得到的结果
DGHEBJIFCA
因为前序访问得到的序列是
访问根节点+访问左子树+访问右子树
那么得到中序访问的序列是
访问左子树+访问根节点+访问右子树
那么前序序列的第一位肯定会在中序序列中 那么再中序序列前面的那一段就是前序序列的左子树,右边一段就是前序序列的右子树,那么这时候递归重复上述过程,当一个节点的左子树全部找到和右子树全部找到,那么说明可以输出根节点了
ps:其实这个有专业的题解,但是我想自己表达一下,但是还是没有表达清楚,因为这颗二叉树是不重复的,所以可以用上述方法,详细解释传送门
一份简洁的代码
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<vector> #include<cmath> #include<string> #include<queue> #define eps 1e-9 #define ll long long #define INF 0x3f3f3f3f using namespace std; const int maxn=26+10; char first[maxn],mid[maxn]; void dfs(int xx,int yy,int len) { char top=first[xx]; if(yy==len) return; int x=0; for(int i=yy;i<len;x++,i++) { if(mid[i]==top) break; } dfs(xx+1,yy,yy+x); dfs(xx+1+x,yy+x+1,len); printf("%c",top); } int main() { while(~scanf("%s%s",first,mid)) { int len=strlen(first); dfs(0,0,len); } return 0; }
二叉树的有趣问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。