首页 > 代码库 > 二叉树的有趣问题

二叉树的有趣问题

近期看了一下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;
}




二叉树的有趣问题