uva_548-Tree

[cpp]
/**中序，后序建树，然后遍历，求根到叶子的最小和，输出
 *该叶子节点，关于通过二叉树建树问题，本博客有相关讲述。。。
 */ 
#include <cstdio> 
#include <cstring> 
#include <algorithm> 
using namespace std; 
 
struct Node { 
    int v; 
    Node *lc, *rc; 
}; 
 
#define MAX 10001 
#define MAXN 700001 
#define INF 0x7fffffff 
 
 
char str1[MAXN], str2[MAXN]; 
int order[MAX], post[MAX]; 
int len, minv, ans; 
 
int find(int c, int pos, int n){ 
    for(int i = pos; i <= n; i ++){ 
        if( c == order[i] ) return i; 
    } 
    return -1; 
} 
 
void post_order_create_tree(Node *&root, int r, int m, int length){ 
    if( length <= 0 ) { root = NULL; return ;} 
 
    root = new Node; 
    root->v = post[r]; 
    int pos = find(post[r], m, length+m); 
    int leftlen = pos - m; 
    int rightlen = length - leftlen - 1; 
 
    post_order_create_tree(root->lc, r-1-rightlen, m, leftlen); 
    post_order_create_tree(root->rc, r-1, pos+1, rightlen); 
} 
 
void find_min(Node* root, int sum){ 
    if( !root ) return; 
    sum += root->v; 
    if(!root->lc && !root->rc){ 
        if(minv > sum){ 
            minv = sum; 
            ans = root->v; 
        }else if( minv == sum ){ 
            ans = min(ans, root->v); 
        } 
        return ; 
    } 
    find_min(root->lc, sum); 
    find_min(root->rc, sum); 
 
} 
 
void print(Node *root){ 
    if( !root ) return ; 
    printf("%d ",root->v); 
    print(root->lc); 
    print(root->rc); 
} 
 
int main(int argc, char const *argv[]) 
{ 
#ifndef ONLINE_JUDGE 
        freopen("test.in", "r", stdin); 
        //freopen("test.out", "w", stdout); 
#endif 
    int length; 
    Node *root; 
    while( gets(str1) > 0){ 
        gets(str2); 
        length = 0; 
         minv = ans = INF; 
        for(int i = 0; str1[i] != '\0'; i ++){ 
            if( str1[i] == ' ' ) { length ++; continue;} 
            order[length] *= 10; 
            order[length] += str1[i] - '0'; 
        } 
        length = 0; 
        for(int i = 0; str2[i] != '\0'; i ++){ 
            if( str2[i] == ' ' ) { length ++; continue;} 
            post[length] *= 10; 
            post[length] += str2[i] - '0'; 
        } 
        length ++; 
        len = length; 
        post_order_create_tree(root, length-1, 0, length); 
        find_min(root, 0); 
        printf("%d\n",ans); 
        memset(order, 0, sizeof(int) * length); 
        memset(post, 0, sizeof(int) * length); 
    } 
    return 0; 
} 

补充：软件开发 , Java ,