前序中序转后序

输入#1

1
2
ABEDFCHG
CBADEFGH

输出#1

1
AEFDBHGC

针对二叉树的

前序遍历，根->左->右

中序遍历，左->根->右

这两个的特性

我们可以尝试凭借前序遍历的根结点（叶子结点也可以看错左右儿子为空的根）将中序遍历的左右根依次拆分成左右两块，针对左右两块再次递归操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void _find(string InOrderStr, string PreOrderStr){
	if (PreOrderStr.empty())return;//针对前序遍历序列（拆分出的序列的）的根结点访问结束
    
    char root = PreOrderStr[0];
    PreOrderStr.erase(PreOrderStr.begin());//根结点取出，作为拆分标识
    
    int rootidx = InOrderStr.find(root);
    
    string leftIn = InOrderStr.substr(0,rootidx);		//中序左分块
    string leftPre = PreOrderStr.substr(0,rootidx);		//新前序，内容与中序 左 分块相同
    
    string rightIn = InOrderStr.substr(rootidx + 1);	//中序右分块
    string rightPre = PreOrderStr.substr(rootidx);			//新前序，内容与中序 右 分块相同
    
    _find(leftIn,leftPre);	//左分块递归
	_find(rightIn,rightPre);//右分块递归
    
    cout << root;
}

后序中序转前序(和上方概念类似)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
stack<char> st;

int main() {
	string InOrderStr;
	string PreOrderStr;
	cin >> InOrderStr >> PreOrderStr;
	
	_find2(InOrderStr, PreOrderStr);
	while (!st.empty()) {
		cout << st.top();
		st.pop();
	}

	return 0;
}

void _find2(string InOrderStr, string PostOrderStr){
	if (PostOrderStr.empty())return;
	char root = PostOrderStr[PostOrderStr.size() - 1];
	PostOrderStr.pop_back();

	int rootidx = InOrderStr.find(root);

	string leftIn = InOrderStr.substr(0, rootidx);
	string leftPost = PostOrderStr.substr(0, rootidx);

	string rightIn = InOrderStr.substr(rootidx + 1);
	string rightPost = PostOrderStr.substr(rootidx);


	_find2(rightIn, rightPost);
	_find2(leftIn, leftPost);

	st.push(root);
}