1127. ZigZagging on a Tree (30)

https://www.patest.cn/contests/pat-a-PRactise/1127

我想到一种直接暴力的方法，就是中序后序建树以后，直接用一个双向队列进行层序遍历，

//第一种思路//我的思路就是用了一个deque//从第二层开始，当遍历偶数层数时，左边队头出去，右边进来，//奇数层数时，deque右边出去，左边进来。#include <iostream>#include <cstdio>#include <deque>using namespace std;const int maxn = 35;int in[maxn];int post[maxn];struct node {	int data;	node *lchild;	node *rchild;};//inOrder和postOrder 创建 树/*    inOrder:12 11 20 17 1 15 8 5    postOrder:12 20 17 11 15 8 5 1*/// use the inOrder and postOrder create the binary tree//node *Create(int postL, int postR, int inL, int inR) {	if ( postL > postR ) return NULL;	node *root = new node();	root->data = post[postR];	int index;	for ( index = inL; index <= inR; index++ ) {		if ( in[index] == post[postR] ) break;	}	int numLeft = index - inL;	root->lchild = Create(postL, postL+numLeft-1, inL, index-1);	root->rchild = Create(postL+numLeft, postR-1, index+1, inR);	return root;}// 1 11 5 12 17 8 20 15void SpecialLevelOrder(node *root) {    deque<node*> dq;    node *T;    if ( !root ) return;    dq.push_back(root);//1    bool cnt = false;//来判断偶数和奇数    int n = 0;    //因为末尾不能有空格    T = dq.front();    dq.pop_front();    printf("%d",T->data);    if ( T->lchild ) dq.push_back(T->lchild);    if ( T->rchild ) dq.push_back(T->rchild);    cnt = true;    while ( !dq.empty() ) {        n = dq.size();        if ( cnt ) {            for ( int i = 0; i < n; i++) {                T = dq.front();                printf(" %d",T->data);                if ( T->lchild ) dq.push_back(T->lchild);                if ( T->rchild ) dq.push_back(T->rchild);                dq.pop_front();            }            cnt = false;        }        else { //cnt%2 == 0            for ( int i = 0; i < n; i++ ) {                T = dq.back();                printf(" %d",T->data);                if ( T->rchild ) dq.push_front(T->rchild);                if ( T->lchild ) dq.push_front(T->lchild);                dq.pop_back();            }            cnt = true;        }    }}int main() {	int n;	cin >> n;	for ( int i = 0 ; i < n; i++ ) {		cin >> in[i];	}	for ( int i = 0; i < n; i++ ) {		cin >> post[i];	}	node *root;    root = Create(0,n-1,0,n-1);    SpecialLevelOrder(root);	return 0;}
然后还有一种方法就是利用递归建树的特点，用vector记录下每一层的节点value
#include <iostream>#include <vector>using namespace std;const int maxn = 35;int post[maxn];int in[maxn];vector<int> level[maxn];//每个vector用于存储每一层的个数int len = 0;int maxx = 0;//记录层数struct node{	int v;	int l,r;};void SpecialPre(int root, int start, int ed, int index){	if( start > ed ) return;	int i = start;	while( post[root] != in[i] && i < ed) i++;    maxx = max(maxx, index);	level[index].push_back(post[root]);    //root-end == 7-7 == 0 +	SpecialPre(root-ed+i-1, start, i-1, index+1);	SpecialPre(root-1, i+1, ed, index+1);}int main(){	int n;	cin >> n;	for( int i = 0; i < n; i++ )        cin >> in[i];	for( int i = 0; i < n; i++ )        cin >> post[i];	//post->root, in->start, in->end, index	SpecialPre(n-1,0,n-1,1);	int cnt = n;	int tt = 0;	for( int i = 1; i <= maxx; i++ ) {		if( i%2 == 0 ) {            for(int j = 0; j < level[i].size(); j++ ) {                if( tt == 0 ) cout << level[i][j];                else cout << " " << level[i][j];		  	tt++;		  }		}		else {			for(int j = level[i].size()-1; j >= 0; j--) {                if( tt == 0 ) cout << level[i][j];                else cout << " " << level[i][j];                tt++;            }		}	}    return 0;}