整体逻辑和前序中序、后序中序重建二叉树是一样的。
只不过这次是层序中序重建二叉树。
前序中序方便就方便在确定了根的位置之后,左右子树就能够根据长度分开,但是这里层序并不是那么容易分开,解决的办法就是枚举一下,确定好下一步的左右子树的层序序列分别是什么,然后丢进build的参数里面。
#include<iostream>
using namespace std;
void build(string in_order, string layer_order) {
char root = layer_order[0];
cout << root;
int t = -1;
for (int i = 0; i < in_order.size(); i ++)
if (in_order[i] == root) {
t = i;
break;
}
// in_order: [0, t - 1], [t + 1, ]
string lin_order = in_order.substr(0, t);
string rin_order = in_order.substr(t + 1);
string l_layer_order, r_layer_order;
for (char c : layer_order) {
for (char lc : lin_order)
if (c == lc) {
l_layer_order.push_back(c);
break;
}
for (char rc : rin_order)
if (c == rc) {
r_layer_order.push_back(c);
break;
}
}
if (lin_order.size()) build(lin_order, l_layer_order);
if (rin_order.size()) build(rin_order, r_layer_order);
}
int main() {
string in_order, layer_order;
cin >> in_order >> layer_order;
build(in_order, layer_order);
cout << endl;
return 0;
}