前序和中序转后序的问题？

Question

#include
#include
using namespace std;
vector pre, in;
bool flag = false;
void postOrder(int prel, int inl, int inr) {
if (inl > inr || flag == true) return;
int i = inl;
while (in[i] != pre[prel]) i++;
postOrder(prel+1, inl, i-1);
postOrder(prel+i-inl+1, i+1, inr);//这个prel+i-inl+1是什么意思我没看懂有谁能知道的吗
if (flag == false) {
printf("%d", in[i]);
flag = true;
}
}
int main() {
int n;
scanf("%d", &n);
pre.resize(n);
in.resize(n);
for (int i = 0; i < n; i++) scanf("%d", &pre[i]);
for (int i = 0; i < n; i++) scanf("%d", &in[i]);
postOrder(0, 0, n-1);
return 0;
}
这个是浙大pat1138Postorder Traversal上的问题，不加-inl而是传统的prel+i+1则会超时。

Answer 1

为了便于理解，我这里只讲第一层的递归，之后的层数同理可得。
i记下的是树根的下标，所以理论上已经知道左子树有哪些结点，右子树有哪些结点（因为遍历序列左子树都在右子树之前），所以你这个时候要做的是把左子树和右子树分开，然后分别进行递归。
而这个时候你需要知道参数，你的参数包括：
前序的最左端的下标（也就是相应子树的树根），中序序列的最左端下标和最右端下标。
所以我们先来看左子树：整棵树的树根的下标是prel，所以左子树的根的下标是prel + 1，然后中序序列的左子树的下标是从inl到i - 1。
而右子树的后面两个参数也是同样的，右子树的中序序列的最左端下标是i + 1，最右端下标是inr，而右子树的根的下标是谁呢？
刚刚提到过，左子树和右子树的遍历一定是左子树都在右子树之前，而中序序列左子树有多少个结点是非常容易求得的：i - inl，所以前序的左子树的结点数也是i - inl，prel + (i - inl) +1的意思是不是就很明确了？就是右子树的根的下标。
画个图就更容易理解了，你可以试试画图看看。

我是小韦同学，企者不立，跨者不行，每天进步一点点。
如果这个题还有疑问可以给我发邮件，邮箱：[e-mail]