03-树3 Tree Traversals Again (25 分)

今天在学习数据结构，刷作业时遇到这个问题，题目隐含条件挖掘出来以后就是根据先序遍历和中序遍历，然后让你推出后序遍历的结果。

一开始我就想到可以用循环，但是写着写着发现有点复杂，为什么不用递归呢？
递归肯定是可以，但是我遇到一个问题，就是思路感觉是对的，但是结果总是不对，后来我换成自己构造的简单测试案例然后一步一步跑，最后发现是由于函数使用的是值传递，在每次递归里面对传进去的东西修改以后，无法传出来，所以果断改用引用，果然对了！
但是提交以后发现递归爆栈了。。果然递归大法好，一直爆栈一直爽。。

#include<iostream>
#include<vector>
#include<string>
using namespace std;
int CountLeft(vector<int>V, int X) {
	int count = 0;
	for (int i = 0; i < V.size(); i++) {
		if (V[i] != X)count++;
		else break;
	}
	return count;
}
int CountRight(vector<int>V, int X) {
	int i=999999, count = 0;
	for (int j = 0; j < V.size(); j++) {
		if (V[j] == X) {
			i = j;
		}
		if (j > i)count++;
	}
	return count;
}
int flag = 1;
vector<int>S;
void Search(vector<int>&V1, vector<int>&V2) {
	int lef = CountLeft(V2, V1[0]);
	int righ = CountRight(V2, V1[0]);
	int root = V1[0];
	V1.erase(V1.begin());
	if (lef != 0) {
		vector<int>tmp1;
		tmp1.insert(tmp1.begin(), V2.begin(), V2.begin() + lef);
		Search(V1, tmp1);
		
	}
	if (righ != 0) {
		vector<int>tmp;
		tmp.insert(tmp.begin(), V2.begin() + lef + 1, V2.end());
		Search(V1, tmp);
	
	}
	if (flag == 1) { cout << root; flag = 0; }
	else { cout << " " << root; }
}
int main() {
	int N;
	string s;
	scanf("%d", &N);
	cin.ignore();
	vector<int>V1, V2, V3;
	for (int i = 0; i < 2*N; i++) {
		getline(cin, s);
		if (s.length() == 6) {
			V1.push_back(s[5] - '0');
			V2.push_back(s[5] - '0');
		}
		else {
			int tmp = V1[V1.size() - 1];
			V3.push_back(tmp);
			V1.pop_back();
		}
	}
	Search(V2, V3);
	return 0;
}

我试着修改成循环吧。。
修改过后的代码

#include<iostream>
#include<string>
#include<vector>
using namespace std;
vector<int>V1, V2, V3, V4;
void postorder(int root, int start, int end) {
	if (start >end)return;
	int i = start;
	while (i < end&&V3[i] != V2[root])i++;
	postorder(root + 1, start, i - 1);
	postorder(root + i - start + 1, i + 1, end);
	V4.push_back(V2[root]);
}
int main() {
	int N, value;
	string s;
	scanf("%d", &N);
	cin.ignore();
	for (int i = 0; i < 2 * N; i++) {
		cin >> s;
		if (s.length() == 4) {
			cin >> value;
			V1.push_back(value);
			V2.push_back(value);
		}
		else {
			int tmp = V1[V1.size() - 1];
			V3.push_back(tmp);
			V1.pop_back();
		}
	}
	postorder(0, 0, N - 1);
	for (int i = 0; i < V4.size(); i++) {
		if (i == 0)cout << V4[0];
		else cout << " " << V4[i];
	}
	return 0;
}

得出一个很重要结论就是：尽量减少在递归里面进行计算，不然很容溢出；

好吧还有第三个版本，建立索引，对索引进行操作，膜拜柳神

#include<iostream>
#include<string>
#include<vector>
#include<stack>
using namespace std;
vector<int>V1, V2, V3, V4;
void postorder(int root, int start, int end) {
	if (start >end)return;
	int i = start;
	while (i < end&&V3[i] != V2[root])i++;
	postorder(root + 1, start, i - 1);
	postorder(root + i - start + 1, i + 1, end);
	V4.push_back(V2[root]);
}
int main() {
	int N, value, key = 0;
	string s;
	stack<int>S;
	scanf("%d", &N);
	cin.ignore();
	for (int i = 0; i < 2 * N; i++) {
		cin >> s;
		if (s.length() == 4) {
			cin >> value;
			V1.push_back(value);//顺序值表
			V2.push_back(key);//顺序索引
			S.push(key++);
		}
		else {
			V3.push_back(S.top());//中序索引
			S.pop();
		}
	}
	postorder(0, 0, N - 1);
	for (int i = 0; i < V4.size(); i++) {
		if (i == 0)cout << V1[V4[0]];
		else cout << " " << V1[V4[i]];
	}
	return 0;
}

在此总结一下递归的经验（新手菜鸡，第一天接触递归。）
①：找到宏观写法，意思就是拿分而治之就是把左边看成新的整体，右边看成新的整体，调用本函数处理左边，处理右边。
②：找到边界条件，意思就是合适退出递归，返回上一层。
③：尽量减少递归里调用其他函数，很容易爆栈。。。