1020. Tree Traversals 解析

我是直接由后序 和中序建树 然后 层序遍历。

#include <iostream>#include <vector>#include <queue>using namespace std;vector <int> post;vector <int> in;int N, Count = 0;struct Node {	int data;	Node * L;	Node * R;};typedef Node * Tree;Tree BuildTree(int inst,int ined, int postst ,int posted) {	Tree t = new Node;#ifdef _DEBUG	cout << "in: " << inst << " " << ined ;	cout << " Post: " << postst << " " << posted << endl;#endif	if (postst <= posted) {		t->data = post[posted];#ifdef _DEBUG		cout << post[posted] << endl;#endif		int L = 0; int R = 0; int tempI = 0;		bool isFind = false, isLR = false;		for (int i = inst; i <= ined; i++) {			if (in[i] == post[posted]) {				isFind = true;				isLR = true;				tempI = i;			}			if (!isLR) L++;			else R++;		}		R--;#ifdef _DEBUG		cout << "L " << L << " R " << R << endl;#endif		if (isFind) {			t->L = BuildTree(inst, tempI - 1, postst, postst + L - 1);			t->R = BuildTree(tempI + 1, ined, postst + L, posted - 1);		}		else return NULL;	}	else t = NULL;	return t;}void PReOrder(Tree T) {	if(T){		cout << T->data << " ";		PreOrder(T->L);		PreOrder(T->R);	}}vector <int> s;void LevelOrder(Tree T) {	queue <Tree> q;	Tree temp;	if (T) {		q.push(T);		while (!q.empty()) {			temp = q.front();//			cout << q.size() << endl;			s.push_back(temp->data);			q.pop();			if (temp->L) q.push(temp->L);			if (temp->R) q.push(temp->R);		}	}}int main() {	int  temp;	cin >> N;	for (int i = 0; i < N; i++) {		cin >> temp;		post.push_back(temp);	}	for (int i = 0; i < N; i++) {		cin >> temp;		in.push_back(temp);	}	Tree T = BuildTree(0,N-1,0,N-1);	//PreOrder(T);	LevelOrder(T);		for (int i = 0; i < s.size() - 1; i++) {		cout << s[i] << " ";	}	cout << s[s.size()- 1] << endl;	system("pause");	return 0;}