uva 548 Tree

思路: 數據結構
分析:
1 題目給定一棵二叉樹的中序序列和後序序列求這個二叉樹裡面，根節點到葉子節點的最短路徑的葉子節點的值，如果有多條路徑輸出最小的葉子節點
2 題目說最多有10000個節點，但是由於題目所說的二叉樹並不是完全二叉樹，所以這裡建立二叉樹並不能夠利用靜態的思想，應該要利用動態的增加
3 建立了二叉樹之後，只要按照前序遍歷的思路即可求出ans

代碼:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int INF = 1<<30;
const int MAXN = 1000010;

struct Node{
    int x;
    Node *left;
    Node *right;
    Node(int x){
        this->x = x;
        this->left = NULL;
        this->right = NULL;
    }
};
Node *root;

char str[MAXN];
int nodeNum , ans , maxNum , stepNum;
int midOrder[MAXN] , postOrder[MAXN];

void getOrder(int *arr){
    int len = strlen(str);
    nodeNum = 0;
    for(int i = 0 ; i < len ; i++){
        int j = i;
        int num = 0;
        while(str[j] != ' ' && j < len){
            num = num*10 + str[j]-'0';
            j++;
        }
        arr[nodeNum++] = num;
        i = j;
    }
}

Node* createTree(int *mid , int *post , int len){
    if(len == 0)
        return NULL;
    int k = 0;
    while(mid[k] != post[len-1])
        k++;
    Node *root = new Node(post[len-1]);
    // 左子樹
    root->left = createTree(mid , post , k); 
    // 右子樹
    root->right = createTree(mid+k+1 , post+k , len-k-1); 
    return root;
}

void solve(int sum , int step , Node *node){
    if(node != NULL){
        if(node->left == NULL && node->right == NULL){
            if(maxNum > sum+node->x){
                maxNum = sum+node->x; 
                ans = node->x; 
            }   
            else if(maxNum == sum+node->x)
                ans = min(ans , node->x);
        }
        solve(sum+node->x , step+1 , node->left);
        solve(sum+node->x , step+1 , node->right);
    }
}    

int main(){
    while(gets(str)){ 
        getOrder(midOrder); 
        gets(str);
        getOrder(postOrder);

        root = createTree(midOrder , postOrder , nodeNum);
        maxNum = ans = INF;
        solve(0 , 0 , root);
        printf("%d\n" , ans);
    } 
    return 0;
}