推断二叉树(递推)

已知前序中序求后序

#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
void binary_tree(string mid, string pre) {
	if (mid.size() > 0) {
		char ch = pre[0];
		int cur = mid.find(ch);
		binary_tree(mid.substr(0, cur), pre.substr(1, cur));
		binary_tree(mid.substr(cur + 1), pre.substr(cur + 1));
		cout << ch;
	}
}

int main() {
	string a, b;
	cin >> a >> b;
	binary_tree(a, b);
	return 0;
}

已知后序中序求前序

#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std; void binary_tree(string mid, string last)
{
	if (mid.size() > 0)
	{
		char ch = last[last.size() - 1];
		cout << ch;
		int cur = mid.find(ch);
		binary_tree(mid.substr(0, cur), last.substr(0, cur));
		binary_tree(mid.substr(cur + 1), last.substr(cur, last.size() - cur - 1));
	}
}

int main()
{
	string a, b;
	cin >> a >> b;
	binary_tree(a, b);
	return 0;
}