算法刷题——树(Uva 548)

  |   0 评论   |   0 浏览

1.题目描述

给定一棵点带权(权值各不相同,都是小于 10000 的正整数)的二叉树的中序和后序遍历,找到一个叶子使得它到路径上的权和最小。如果有多解,该叶子本身的权应尽量小。输入中每两行表示一棵树,其中第一行为中序遍历,第二行为后序遍历。


样例输入

3 2 1 4 5 7 6
3 1 2 5 6 7 4
7 8 11 3 5 16 12 18
8 3 11 7 16 18 12 5
255
255

样例输出

1
3
255


2. 问题分析

  1. 首先建立二叉树的数据结构,根据输入的中序和后序遍历,生成对应的二叉树。
  2. 再根据建立的二叉树,遍历整个树,得到与根之间路径最小的叶子。
  3. 可以定义函数 cal(node* root, int sum) ,用来递归计算以 root 为根节点的子树上的叶子到原二叉树根节点的最短路径,sum 为该子树根节点到 root 的路径长度。

3. Mycode

#include <iostream>
#include <sstream>
/**
Date:2020/1/5
Author:YC
*/
using namespace std;
const int maxn = 10000;
int mid[maxn];
int post[maxn];
int nodes;
int minsum,minleaf;

struct node{
    int val;
    node* l = NULL;
    node* r = NULL;
    node(int v):val(v){}
};

node* init_tree(int *m,int* p ,int sz){
    node* root = new node(p[sz-1]);
    int lsz = 0; //how many nodes on the left tree
    int* t;
    for(t = m; *t != p[sz-1]; t++) lsz++;
    if(lsz > 0)
        root->l = init_tree(m,p,lsz);
    if(sz - lsz - 1 > 0)
        root->r = init_tree(t+1,p+lsz,sz - lsz - 1);
    return root;
}

void cal(node* node,int sum){
    if(!node->l &&!node->r){
        sum+= node->val;
        if(sum < minsum){
            minsum = sum;
            minleaf = node->val;
        }else if(sum == minsum&&node->val < minleaf){
            minleaf = node->val;
        }
    }
    if(node->l)
        cal(node->l, sum + node->val);
    if(node->r)
        cal(node->r, sum + node->val);
}

void del_tree(node* node){
    if(!node) return;
    del_tree(node->l);
    del_tree(node->r);
    delete node;
}

inline void Do(){
    string s1,s2;int ind;node* r;
    while(getline(cin,s1)){
        getline(cin,s2);
        stringstream ss1(s1);
        stringstream ss2(s2);
        ind = 0;
        while(ss1>>mid[ind]) ss2>>post[ind++];
        r = init_tree(mid,post,ind);
        minsum = 1 << 30;
        cal(r,0);
        del_tree(r);
        cout<<minleaf<<endl;
    }

}
int main()
{
    Do();
    return 0;
}

标题:算法刷题——树(Uva 548)
作者:YaoCheng8667
地址:https://ycisme.xyz/articles/2020/01/07/1578378893716.html