POJ-2255 Tree Recovery(给前序和中序求后序)

题目链接
题目大意就是多组输入,给你二叉树的前序和中序遍历,求出后序遍历。
何为前序(DLR)中序(LDR)后序(LRD),看下图。

代码如何实现?

void PreOrder(BTreeNode* BT) {
    if(BT != NULL) {
        cout << BT->data << ' ';     //访问根结点
        PreOrder(BT->left);          //前序遍历左子树
        PreOrder(BT->right);         //前序遍历右子树
    }
}
void InOrder(BTreeNode* BT) {
    if(BT != NULL) {
        InOrder(BT->left);          //中序遍历左子树
        cout << BT->data << ' ';    //访问根结点
        InOrder(BT->right);         //中序遍历右子树
    }
}
void PostOrder(BTreeNode* BT) {
    if(BT != NULL) {
        PostOrder(BT->left);        //后序遍历左子树
        PostOrder(BT->right);       //后序遍历右子树
        cout << BT->data << ' ';    //访问根结点
    }
}

代码:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
void build(int n,char * pre,char * in)
{
    if(n<=0)
        return ;//结束条件,这个很迷啊,没有它你也会卡住
    int nn=strchr(in,pre[0])-in;//寻找字符pre[0]在in字符串中的位置
    build(nn,pre+1,in);//详情想知道为什么戳最后面面链接
    build(n-nn-1,pre+nn+1,in+nn+1);//说到这,这个char* 就很迷了,
    //就拿pre+nn+1来说,代表的是从nn+1开始的,就是把nn+1前面的字符给截去了
    cout<<pre[0];//在这里直接输出节点就ok了

}
int main()
{
    char pre[30],in[30];//这里不能用char *来定义,否则会卡住
    while(~scanf("%s%s",pre,in))
    {
        build(strlen(pre),pre,in);
        cout<<endl;
    }
}

详情描述为何这样递归的博客,请戳这里

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-09 12:02
ssob上原来真有BOSS啊
硫蛋蛋:这种也是打工的,只不是是给写字楼房东打工
点赞 评论 收藏
分享
06-17 21:57
门头沟学院 Java
白友:噗嗤,我发现有些人事就爱发这些,明明已读不回就行了,就是要恶心人
点赞 评论 收藏
分享
06-26 22:20
门头沟学院 Java
码农索隆:让你把简历发给她,她说一些套话,然后让你加一个人,说这个人给你改简历,然后开始卖课
我的求职精神状态
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务