1127. ZigZagging on a Tree 解析

后序中序建树，然后标记层数。奇数层用个stack倒个序就好。

#include <iostream>#include <queue>#include <vector>#include <algorithm>#include <stack>#define MAX 35using namespace std;struct Node {	int data;	Node * Left; 	Node * Right;	int level;	Node() { Left = NULL; Right = NULL; };};typedef Node * Tree;int post[MAX];int in[MAX];int n;vector <int> ans;int FindIn(int inst, int ined ,int num) {	for (int i = inst; i <= ined; i++) {		if (in[i] == num)			return i;	}	return -1;}Tree BuildTree(int inst,int ined,int postst,int posted) {	Tree t = NULL;	if ((inst <= ined) && (postst <= posted)) {		t = new Node;		t->data = post[posted];		int pos = FindIn(inst, ined, post[posted]);		if (pos == -1)			return NULL;		t->Left = BuildTree(inst, pos - 1, postst, postst + pos - inst -1);		t->Right = BuildTree(pos + 1, ined, postst + pos - inst, posted - 1);	}	return t;}//Tree BuildTree(int inst, int ined, int postst, int posted) {//	Tree t = new Node;////	if (postst <= posted) {//		t->data = post[posted];////		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--;// //		if (isFind) {//			t->Left = BuildTree(inst, tempI - 1, postst, postst + L - 1);//			t->Right = BuildTree(tempI + 1, ined, postst + L, posted - 1);//		}//		else return NULL;//	}//	else t = NULL;////	return t;////}void Level(Tree t) {	queue <Node> q;	stack <int> s;	int PRe;	int level = 1;	bool newlevel = false;	if (t) {		pre = t->data;		t->level = 1;		pre = 1;		q.push(*t);		while (!q.empty()) {			Node temp = q.front();			if (pre != temp.level) {				pre = temp.level;				newlevel = true;			}			if (newlevel) {				while (!s.empty()) {					ans.push_back(s.top());					s.pop();				}				newlevel = false;			}				if (temp.level % 2 == 1) {					s.push(temp.data);				}				else {					ans.push_back(temp.data);				}			if (temp.Left) temp.Left->level = temp.level + 1, q.push(*temp.Left);			if (temp.Right) temp.Right->level = temp.level + 1, q.push(*temp.Right);			q.pop();		}		while (!s.empty()) {			ans.push_back(s.top());			s.pop();		}	}}int main() {	cin >> n;		for (int i = 1; i <= n; i++) {		cin >> in[i];	}	for (int i = 1; i <= n; i++) {		cin >> post[i];	}	Tree T = BuildTree(1,n,1,n);	Level(T);	for (int i = 0; i < ans.size()-1; i++) {		cout << ans[i] << " ";	}	if (ans.size() > 1) {		cout << ans[ans.size() - 1] << endl;	}	else if (ans.size() == 1) {		cout << ans[0] << endl;	}	return 0;}