[UVa] 548 - Tree

參考入門經典一書的程式碼
改以struct建構樹的方式進行改寫
許多細節需要注意

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <iostream>
#include <sstream>
using namespace std;
bool failed;
const int maxn = 10010;
int i=0,inorder[maxn], postorder[maxn];

struct Node{
    bool have_value;
    int v;
    Node *left, *right;
    Node():have_value(false),left(NULL),right(NULL){};
};
Node *root;

Node* newnode(){
    return new Node();
}

void remove_tree(Node* u){
    if(u==NULL)return;
    remove_tree(u->left);
    remove_tree(u->right);
    delete u;
}

Node* buildtree(int L1, int R1, int L2, int R2){
    if(L1>R1)return NULL;
    Node* u = newnode();
    u->v = postorder[R2];
    u->have_value = true;
    int p = L1;
    while(inorder[p] != u->v)p++;
    int count = p-L1; //nodes of left tree

    u->left = buildtree(L1,p-1,L2,L2+count-1);
    u->right = buildtree(p+1,R1,L2+count,R2-1);
    return u;
}

int best_sum, best;
void dfs(Node* u, int sum){
    sum = sum + u->v;
    if(u->right==NULL && u->left==NULL)
        if(sum<best_sum || (sum==best_sum && u->v < best)){
            best_sum = sum;
            best = u->v;
        }
    if(u->right){
        dfs(u->right, sum);
    }
    if(u->left){
        dfs(u->left, sum);
    }

}

/*
//顯示樹有無建立成功使用
int n=0;
vector<int> ans;
bool bfs(){
    queue<Node*> q;
    ans.clear();
    q.push(root);
    while(!q.empty()){
        Node* u = q.front(); q.pop();
        if(!u->have_value) return false;
        ans.push_back(u->v);
        n++;
        if(u->left != NULL)q.push(u->left);
        if(u->right != NULL)q.push(u->right);
    }
    return true;
}
*/

int main(){
    string line;
    while(getline(cin,line)){
        i=0;
        int x;
        stringstream ss(line);
        while(ss>>x){
            inorder[i]=x;
            i++;
        }
        int L1=0,R1=i-1;
        //for(int k=0;k<i;k++)printf("%d\n",inorder[k]);
        i=0;
        getline(cin,line);
        stringstream ss2(line);
        while(ss2>>x){
            postorder[i]=x;
            i++;
        }
        int L2=0,R2=i-1;
        //for(int k=0;k<i;k++)printf("%d\n",postorder[k]);
       
        root = buildtree(L1,R1,L2,R2);
        best_sum = 10000000;

        dfs(root,0);
        printf("%d\n",best);
        remove_tree(root);
        /*
        bfs();
        for(int j=0;j<ans.size()-1;j++){
            printf("%d ",ans[j]);
        }
        */
    }

    return 0;
}