[NOIP 2001 普及组] 求先序排列

知识点

二叉树、树的遍历、递归

解题思路

后序串的末字符是根。在中序串找到根，左侧为左子树，右侧为右子树；据左子树长度切分后序串。先输出根，再递归处理左、右子树。

正确性说明

中序遍历的根两边分别恰为左右子树，后序在根前按左、右顺序排列。节点字符互异，根位置和切分唯一。对子树归纳，根+左前序+右前序即正确前序。

易错点

单节点和只有一侧孩子；切分后序时不能把末尾根带入右子树。

复杂度

该实现查找及复制子串，时间O(n²)，递归栈O(n)，n≤8。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
string pre(string in,string post){if(in.empty())return "";char r=post.back();int k=in.find(r);return string(1,r)+pre(in.substr(0,k),post.substr(0,k))+pre(in.substr(k+1),post.substr(k,post.size()-k-1));}int main(){string a,b;cin>>a>>b;cout<<pre(a,b)<<'\n';}