uva 548 Tree

题目意思：给定一颗二叉树后序和中序，求出这颗二叉树从根节点到叶子点的和的最小值，输出最小值的叶子节点的值

解题思路：1利用模板建立一颗二叉树 2 遍历求最小的和的叶子节点的值

代码：

[cpp] 
<span style="font-size:18px;"> 
#include <cctype> 
#include <iostream> 
#include <cstdio> 
#include <string> 
#include <cstring> 
using namespace std; 
 
const int MAXN = 100010; 
//结构体的结构 
struct Btree{ 
    int val; 
    struct Btree *lchild; 
    struct Btree *rchild; 
    struct Btree *father;//定义一个父亲指针 
}; 
Btree *root , *temp; 
int  post[MAXN] , mid[MAXN]; 
int  len , nodesum[MAXN] , node[MAXN];//用来存储最小的叶子节点的值 
int  pathnum[MAXN] , Minsum , Minnode , sum; 
 
 
//初始化二叉树 
void newBtree(Btree *u){ 
    u -> lchild = NULL; 
    u -> rchild = NULL; 
    u -> father = NULL; 
} 
 
//建树（使用模板见我的博客） 
Btree* InPostCreateTree(int *mid , int *post , int len){ 
    if(len == 0) 
           return NULL; 
        int i = len-1; 
        while(post[len-1] != mid[i]) 
        --i; 
        Btree *root = new Btree; 
    newBtree(root); 
    root -> val = post[len-1]; 
    root -> lchild = InPostCreateTree(mid,post,i); 
    root -> rchild = InPostCreateTree(mid+i+1,post+i,len-i-1); 
    return root; 
} 
 
//输入函数(先输入中序) 
int input(){ 
    char space; 
    int i , j , n , len , count = 0; 
    i = 1;j = 0; 
    while(scanf("%d%c" , &n , &space)){ 
        if(count == 0){ 
            mid[i] = n; 
            i++; 
        } 
        if(count == 1){ 
            post[j] = n; 
            j++; 
        } 
        if(space == '/n') 
            count++; 
        if(count == 2) 
            break; 
    } 
    return i;  
} 
 
//求解最小路径值的叶子节点 
//我们用一个index来表示当前的位置，用tempsum数组存储读入的值，只要到了叶子节点就计算上面一次的和，更新Minsum 和 Minnode 
void minpath(Btree *root , int Index){ 
        if(root==NULL) return ;  //注意加上这一句 
        if(root -> lchild == NULL && root -> rchild == NULL){//如果为叶子节点 
            pathnum[Index] = root -> val;//这句重点 
            for(int i = 0 ; i <= Index ; i++) 
               sum += pathnum[i];//求到该叶子节点的和 
            if(Minsum > sum){//是否更新 
               Minsum  = sum; 
               Minnode = pathnum[Index];  
            } 
            sum = 0;//注意每一计算完为0 
            --Index;//向上一步 
            return; 
        }         
    if(root != NULL){ 
        pathnum[Index] = root->val;//每次把值存入数组 
        minpath(root->lchild , Index+1);//注意参数的传入 
        minpath(root->rchild , Index+1); 
    } 
} 
 
//处理问题函数 
void solve(){ 
    root = new Btree; 
    temp = new Btree; 
    newBtree(root);//初始化，注意new出来后要初始化 
    newBtree(temp); www.2cto.com
    root = InPostCreateTree(mid , post , len); 
    Minsum = 999999999;//开始为大数 
    sum = 0; 
    memset(pathnum , 0 , sizeof(pathnum)); 
    minpath(root , 0); 
    cout<<Minnode<<endl; 
} 
 
//主函数  
int main(){ 
    //freopen("input.txt" , "r" , stdin); 
    int n; 
    char ch; 
    while(~scanf("%d%c" , &n , &ch)){ 
       mid[0] = n; 
        if(ch == '/n'){ 
            scanf("%d" , &post[0]); 
            cout<<mid[0]<<endl; 
            continue; 
        } 
        else 
            len = input(); 
        solve(); 
    } 
    return 0; 
}</span> 

作者：cgl1079743846