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

思路：结构体建树，然后用数组进行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("\n");

	}//while

}