uva 548 - Tree - dblank

uva 548 - Tree

传送门:548 - Tree

题意:给你一个二叉树的中序遍历和后序遍历, 问你这个二叉树那一个叶子节点到根节点的权重和最小,多解取权值最小的叶子节点。

思路:通过中序遍历和后序遍历可以还原树,然后直接dfs就可以求解了。

已知中序遍历和后序遍历,还原二叉树

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 100000 + 10, Mod = 1000000009;
typedef long long ll;
char s[N];
int post[N], in[N], minx, ans;
struct treenode
{
    treenode *left;
    treenode *right;
    int data;
};
treenode build(int post, int *in, int len)
{
    if(len == 0)
    {
        return NULL;//子树建立完毕,返回空
    }
    treenode *node = new treenode;//新的节点
    int id  = 0;
    for(; id<len; id++)
    {
        if(in[id] == post[0])//在中序遍历中找到根节点的位置
            break;
    }
    node->data = post[0];
    //  cout<<node->data;//输出结果为前序
    node->left = build(post+len - id, in, id);//建立左子树
    node->right = build(post+1, in+id+1, len - (id+1));//建立右子树
    return node;//返回该节点
}
void dfs(treenode *root, int sum)
{
    sum += root->data;
    if(root ->left == NULL && root->right == NULL)
    {
      //  cout<<root->data<<endl;
        if(sum<minx)
        {
            minx = sum;
            ans = root->data;
        }
        if(sum == minx && root->data < ans)
        {
            ans = root->data;
        }
        return ;
    }
    if(root->left != NULL)
        dfs(root->left, sum);
    if(root->right != NULL)
        dfs(root->right, sum);
}
int main()
{
    while(gets(s))
    {
        int len = strlen(s);
        int k1 = 0, k2 = 0, num = 0;
        for(int i = 0; i<=len; i++)
        {
            num = 0;
            while(isdigit(s[i]))
            {
                num = num * 10 + s[i] - '0';
                i++;
            }
            in[k1++] = num;
        }
        gets(s);
        len = strlen(s), num = 0;
        for(int i = 0; i<=len; i++)
        {
            num = 0;
            while(isdigit(s[i]))
            {
                num = num * 10 + s[i] - '0';
                i++;
            }
            post[k2++] = num;
        }
        ans = inf;
        minx = inf;
        reverse(post, post+k2);//倒转遍历结果,更加好处理
        treenode *root = new treenode;
        root = build(post, in, k2);
        dfs(root,0);
        printf("%dn", ans);
    }
    return 0;
}

 

相关文章

发表新评论