根据先序遍历跟中序遍历求后序遍历
#include<bits/stdc++.h>using namespace std;
int main(){
string instr,poststr;
cin>>instr>>poststr;
function<void(string,string)>build=[&](string instr,string poststr)
{
//在此补充代码
};
build(instr,poststr);
return 0;
}
//build(instr.substr(0,mid),poststr.substr(0,mid)); //在中序分为左右两个序列
//B B
//DC DCA
根据先序遍历和中序遍历求后续遍历的思路是：首先找出先序遍历的根节点，然后在中序遍历中找到根节点的位置，将中序遍历分为左子树和右子树。接着，再分别对左子树和右子树进行递归操作，直到遍历完所有节点。
下面是一种实现该功能的代码：
#include <iostream>
using namespace std;
void build(string prestr, string instr) {
if (prestr.empty() || instr.empty()) {
return;
}
char root = prestr;// 先序遍历的第一个字符为根节点
int pos = instr.find(root);// 在中序遍历中找到根节点的位置
build(prestr.substr(1, pos), instr.substr(0, pos));// 处理左子树
build(prestr.substr(pos + 1), instr.substr(pos + 1));// 处理右子树
cout << root << " ";// 输出后序遍历结果，即先处理左子树和右子树，最后输出根节点
}
int main() {
string prestr, instr;
cin >> prestr >> instr;
build(prestr, instr);
return 0;
}
输入示例：
ABCD DCBA
输出示例：
DCBA
此代码中，我们首先通过递归的方式找到根节点，并分别递归处理左子树和右子树。最后，按照后序遍历的顺序输出结果。
需要注意的是，该代码假设输入的先序遍历和中序遍历都是合法的，并且没有重复的节点。如果输入不满足这些条件，那么需要对代码进行修改以处理错误情况。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
页:
[1]