URAL 1136 Parliament 二叉樹水題 BST後序遍歷建樹

二叉樹水題，特別是昨天剛做完二叉樹用中序後序建樹，現在來做這個很快的。

跟昨天那題差不多，BST後序遍歷的特型，找到最後那個數就是根，向前找，比它小的那塊就是他的左兒子，比它大的那塊就是右兒子，然後遞歸兒子繼續建樹。

代碼：

 
#include <cstdio>   
#include <cstdlib>   
const int maxn = 70000;  
  
struct Node {  
    int v;  
    Node *l;  
    Node *r;  
};  
int arr[maxn];  
bool flag = false;  
  
Node* addnode(int s, int e) {  
    if (s > e)  
        return NULL;  
    Node* u = (Node*) malloc (sizeof(Node*));  
    u->v = arr[e];  
    if (s == e) {  
        u->r = u->l = NULL;  
        return u;  
    }  
    int i;  
    for (i = e - 1; i >= s; i--)  
        if (arr[i] < arr[e])  
            break;  
    u->l = addnode(s, i);  
    u->r = addnode(i + 1, e - 1);  
    return u;  
}  
  
void output(Node* u) {  
    if (u->r != NULL)  
        output(u->r);  
    if (u->l != NULL)  
        output(u->l);  
    if (flag)  
        printf(" ");  
    flag = true;  
    printf("%d", u->v);  
}  
  
int main() {  
    int n;  
    scanf("%d", &n);  
    for (int i = 1; i <= n; i++)  
        scanf("%d", &arr[i]);  
    Node* root = addnode(1, n);  
    output(root);  
    printf("\n");  
    return 0;  
}  
      

#include <cstdio>
#include <cstdlib>
const int maxn = 70000;

struct Node {
	int v;
	Node *l;
	Node *r;
};
int arr[maxn];
bool flag = false;

Node* addnode(int s, int e) {
	if (s > e)
		return NULL;
	Node* u = (Node*) malloc (sizeof(Node*));
	u->v = arr[e];
	if (s == e) {
		u->r = u->l = NULL;
		return u;
	}
	int i;
	for (i = e - 1; i >= s; i--)
		if (arr[i] < arr[e])
			break;
	u->l = addnode(s, i);
	u->r = addnode(i + 1, e - 1);
	return u;
}

void output(Node* u) {
	if (u->r != NULL)
		output(u->r);
	if (u->l != NULL)
		output(u->l);
	if (flag)
		printf(" ");
	flag = true;
	printf("%d", u->v);
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &arr[i]);
	Node* root = addnode(1, n);
	output(root);
	printf("\n");
	return 0;
}