uva 11234 Expressions 表达式 建树+BFS层次遍历

题目给出一个后缀表达式，让你求从下往上的层次遍历。

思路：结构体建树，然后用数组进行BFS进行层次遍历，最后把数组倒着输出就行了。

uva过了，poj老是超时，郁闷。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>

const int maxn = 10001;
char str[maxn];
int p;

struct Node {
	char data;
	Node* l;
	Node* r;
};

Node* build() {
		Node* u = (Node*) malloc (sizeof(Node*));
		u -> data = str[p];
		p--;
		if (str[p] >= 'A' && str[p] <= 'Z')
		   	u -> l = build();
		else
			u -> l -> data = str[p];
		p--;
		if (str[p] >= 'A' && str[p] <= 'Z')
			u -> r = build();
		else
			u -> r -> data = str[p];
		return u;
}

int main() {
	int t;
	while (scanf("%d", &t) != EOF) {
		scanf("%s", str);
		p = strlen(str) - 1;
		Node* root = build();
		int rear = 0, front = 0;
		Node* q[maxn];
		q[rear++] = root;
		while (rear > front) {
			if (q[front]) {
				if (q[front] -> r) 
					q[rear++] = q[front] -> r;
				if (q[front] -> l) 
					q[rear++] = q[front] -> l;
				front++;
			}
			else
				front++;
		}
		for (int i = rear - 1; i >= 0; i--)
			printf("%c", q[i]->data);
		printf("
");
	}//while
}