题解 P1030 【求先序排列】

旧题新解~

今天做这个题,发现还是没有AC,于是滚回来用了一大堆数据结构A了这个题目,好像复杂度还挺高......

#include <iostream>
#include <cstdio>
#include <stack>
#include <cstring>
#include <map>
#include <algorithm> using namespace std;
char mid[101],late[101];
int mid_[101],late_[101],len=0;
struct tree{
tree *lson,*rson;
int ch;
}rt_,*rt=&rt_;
map<int,char>ic;
map<char,int>ci;
stack<char>qwq; void build(int ch,tree *root);
inline void clear_(tree *root);
void print1(tree *root); int main()
{
clear_(rt);
scanf("%s%s",mid,late);
len=strlen(mid);
for (register int i=0;i<len;i++)
{
ic.insert(make_pair(i+1,mid[i]));
ci.insert(make_pair(mid[i],i+1));
}
for (register int i=0;i<len;i++)
{
late_[i]=ci[late[i]];
}
reverse(late_,late_+len);
for (register int i=0;i<len;i++)
{
build(late_[i],rt);
}
print1(rt);
while (!qwq.empty())
{
putchar(qwq.top());
qwq.pop();
}
return 0;
}
void build(int ch,tree *root)
{
if (root->ch==-1||root->ch==ch)//相等或者是新的节点
{
root->ch=ch;//直接赋值不多说
return ;
}
else if (root->ch<ch)//小于建左树
{
if (root->lson==NULL)//如果没开点就开点
{
root->lson=new tree();
clear_(root->lson);
}
build(ch,root->lson);//递归建左子树
}
else //那就只剩下大于咯
{
if (root->rson==NULL)//如果没开点就开点
{
root->rson=new tree();
clear_(root->rson);
}
build(ch,root->rson);//递归建右子树
}
}
inline void clear_(tree *root)
{
root->lson=root->rson=NULL;
root->ch=-1;
}
void print1(tree *root)//先序排列
{
if (root->lson!=NULL)print1(root->lson);
if (root->rson!=NULL)print1(root->rson);
qwq.push(ic[root->ch]);
}

看看这一长串代码,令人生畏......

首先把题目摆上......

拿过来一看,不就是模拟吗!

但是我们将原先的中序和后序都离散化成二叉搜索树(闲得慌????),就变得好理解了许多(中规中蒟)

原文作者说:

原来如果我们按照颠倒的后序遍历建一个二叉搜索树,然后将输出的字符串存入stack<char>,然后再倒着输出,就完成先序遍历的操作。

感觉有点迷?不要紧,还有一发。

Q1:为什么要颠倒插入?

A:因为后序遍历就是离散化后的从大到小的排序,所以我们将其反转,就可以得到一个先序遍历。按照先序遍历,可以还原整棵树。

Q2:为什么最后要颠倒输出?

因为我们得到的是先序遍历的离散化数据,所以答案反而是逆序的字母串。

Clear?

05-06 06:46