UVa 122 Trees on the level

题目的意思：

输入很多个节点，包括路径和数值，但是不一定这些全部可以构成一棵树，问题就是判断所给的能否构成一棵树，且没有多余。

网上其他大神已经给出了题目意思：比如我一直很喜欢的小白菜又菜的博客

说一声：

之前看了网上好多代码，看的大段大段的，看不下去了，就准备自己写了，结果写出来也是大段大段的，其实中间有不少是被注释掉的测试代码，可忽略不计！

// 测试样例：udebug ：链接

// 我整个代码最核心的整体思想就是把全部节点放到map中，

// 然后层级遍历到的就放到vector(V)中，并从map中删除（重点），最后如果map有剩余就认为not complete!

<span style="font-family:Courier New;font-size:14px;">#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
using namespace std;
struct s{
    string path;   //节点路径
    int value;      //节点值
};
vector <int> v;     //存放可输出的树的节点
map <string, int> m;  //存放树
map <string, int> ::iterator it,it1,it2;
queue <s> q;
//这个地方是重点，就是如何层级输遍历输出；
//在网上看了一下，层级遍历可以用队列，对于每个在队列里面的pop之后，把他的左儿子和右儿子加到队列里（如果有）
void levelordertravel(){
    s temp;
    string t,t1,x,y;
    //如果连根都没有，直接返回了
    it=m.find("");
    if(it!=m.end()) q.push({it->first,it->second});
    else return;
    while(!q.empty()){
        temp=q.front();
        //cout<<temp<<endl;
        v.push_back(temp.value);
        t=temp.path;
        t1=t;
        m.erase(t);
        q.pop();
        //对于每个path，在map找加L和加R的
        x=t.append("L");
        it1=m.find(x);
        y=t1.append("R");
        it2=m.find(y);

        if(it1!=m.end()){
            q.push({it1->first,it1->second});
            //cout<<"left son is in"<<endl;
        }
        if(it2!=m.end()){
            q.push({it2->first,it2->second});
            //cout<<"rigth son is in"<<endl;
        }
    }
}
bool input(){
    string str;
    while(cin>>str){
        string path, value1;
        int value, p, length;
        if(str == "()") break;
        length = str.length();
        p = str.find(',');  //,的位置
        value1 = str.substr(1,p-1);
        value = atoi(value1.c_str());  //这个地方把string转换成int
        path = str.substr(p+1,length-1-(p+1));
        it=m.find(path);
        if(it!=m.end()) path="XXX";
        m[path] = value;
    }
    return !cin.eof();
}
int main()
{
    while(input()){   //这里的输入，没有循环输入的话就会wronganswer 就因为这个问题花费了很久时间
    //int len=m.size();
    //for(it=m.begin();it!=m.end();it++) cout<<it->first<<" "<<it->second<<endl;
    //cout<<endl;
    levelordertravel();
//    for(int i=0;i<v.size();i++){
//            cout<<v[i];
//            if(i!=v.size()-1) cout<<" ";
//        }
//        cout<<endl;
    if(m.size()!=0) cout<<"not complete"<<endl;
    if(m.size()==0){
        for(int i=0;i<v.size();i++){
            cout<<v[i];
            if(i!=v.size()-1) cout<<" ";
        }
        cout<<endl;
    }
    m.clear();
    v.clear();
    }
    return 0;
}</span>

巴特西

UVa 122 Trees on the level

最新文章

热门文章