树 Tree uva548

原题链接

高中信息题就有给你中序遍历和后序遍历让你求前序遍历的题目。这道题就是根据这两个遍历创建出对应的树，然后根据DFS（深度优先搜索）去求出最小路径。

主要代码：

#include<bits/stdc++.h>
using namespace std;
const int Max=10000+10;
int in_node[Max],last_node[Max],cnt=0;
struct node{
    int v;
    node *left,*right;
    node ():left(NULL),right(NULL){}
};
bool input(int a[]){  //中序遍历和后序遍历的读入 
    string s;
    if (!getline(cin,s)) return false;
    stringstream ss(s);
    cnt=0;
    int x;
    while (ss>>x) a[cnt++]=x;
    return true;
}
node* creat_tree(int l1,int r1,int l2,int r2){  //树的创建 
    if (l1>r1 || l2>r2) return NULL;  //边界条件 
    node *root=new node;
    root->v=last_node[r2];  //找到当前子树的根结点 
    int pos=0;
    while (in_node[pos]!=last_node[r2]) pos++;  //从中序遍历中找出该结点位置 
    root->left=creat_tree(l1,pos-1,l2,l2+pos-l1-1);  //左子树的创建 
    root->right=creat_tree(pos+1,r1,l2+pos-l1,r2-1);  //右子树的创建 
    return root;
}
int min_node=0,Min=0;
void dfs(node *root,int sum){  //DFS搜索 
    sum+=root->v;
    if (root->left==NULL && root->right==NULL){  //是叶子结点 
        if (min_node==0 && Min==0){min_node=root->v;Min=sum;}
        else if(sum<Min || (sum==Min && min_node>(root->v))){min_node=root->v;Min=sum;}
    }
    if (root->left!=NULL) dfs(root->left,sum);
    if (root->right!=NULL) dfs(root->right,sum);
}
int main(){
    while (input(in_node)){
        input(last_node);
        node *root=creat_tree(0,cnt-1,0,cnt-1);
        min_node=0,Min=0;
        dfs(root,0);
        cout<<min_node<<endl;
    }
    return 0;
}