uva 548 Tree

点击打开链接uva 548

思路: 二叉树
分析:
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;
}