uva 548 Tree

点击打开链接

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

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

代码：

#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);
    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;
}