UVA 548 Tree 建树

题意：

输入中序和后序的权值，输出哪个叶子使它到根的路径上权和最小。

思路：

输入后建树，然后dfs求最小的叶子。

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<cstring>

 #include<sstream>

 using namespace std;

 int mid[], post[];

 int judge[];

 struct node {

     int index;

     node *left, *right;

     node()

     {

         left = right = NULL;

     }

 };

 int n;

 bool input(int* a)//输入函数

 {

     string line;

     memset(a, , sizeof(a));

     if (!getline(cin, line))

         return false;

     stringstream ss(line);

     int x;

     n = ;

     while (ss >> x)

         a[n++] = x;

     //printf("n=%d\n", n);//

     return n>;

 }

 int cnt, res;

 node* build(node* root, int l, int r)

 {

     int i;

     int t = post[--cnt];

     for (i = l; i<r; i++)

     {

         if (t == mid[i])

             break;

     }

     root = new node();

     root->index = t;

     /* 注意下面是先建右边然后建左边

     因为后序往前走(--cnt)

     */

     if (i<r - )

         root->right = build(root->right, i + , r);

     if (i>l)

         root->left = build(root->left, l, i);

     return root;

 }

 void preorder(node *root)

 {

     printf("%d ", root->index);

     if (root->left != NULL)

         preorder(root->left);

     if (root->right != NULL)

         preorder(root->right);

 }

 int best, best_num;

 void dfs(node *root, int sum)

 {

     sum += root->index;

     if (!root->left && !root->right)

     {

         if (best_num>sum || (sum == best_num&&root->index<best))

         {

             best = root->index;

             //printf("best=%d\n", best);

             best_num = sum;

         }

     }

     if (root->left != NULL)

         dfs(root->left, sum);

     if (root->right != NULL)

         dfs(root->right, sum);

 }

 int main()

 {

     while (input(mid))

     {

         input(post);

         cnt = n;

         //printf("cnt=%d\n", cnt);

         memset(judge, , sizeof(judge));

         node *root = NULL;

         root = build(root, , n);

         best_num = ;

         //preorder(root);

         //printf("\n");

         dfs(root,);

         printf("%d\n",best);

     }

     return ;

 }