UVA 122 Trees on the level 二叉树的层序遍历

　　题目链接： UVA 122

　　题目描述：输入数值和路径，输出一棵树的层序遍历，如果树不合法就输出-1

　　解题思路：纯码力，学会了利用sscanf来赋值，还有就是记住可以把任意“指向字符的指针”看成是字符串，收获很大

　　代码：

#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
#include <list>
#include <iterator>
#include <cmath>
#include <cstring>
#include <forward_list>
using namespace std;

const int maxn = 1000+10;

struct Node {
    int v;
    bool have_value;
    Node * left;
    Node * right;
    Node() {
        left = right = NULL;
        have_value = false;
        v = 0;
    }
}node[maxn];
Node * root;
bool failed;

Node * newnode() {
    return new Node();
}

void addnode(int value, char * s) {
    Node * u = root;
    int n = (int)strlen(s);
    for(int i = 0; i < n; i++) {
        if(s[i] == 'L') {
            if(u->left == NULL) {
                u->left = newnode();
            }
            u = u->left;
        }
        else if(s[i] == 'R'){
            if(u->right == NULL) {
                u->right = newnode();
            }
            u = u->right;
        }
    }
    if(u->have_value) failed = true;
    u->v = value;
    u->have_value = true;
}    

bool read_input() {
    failed = false;
    root = newnode();
    char s[10];
    while(1) {
        if(scanf("%s", s)!=1) return false;
        if(!strcmp(s,"()")) break;
        int v;
        sscanf(&s[1], "%d", &v);
        addnode(v, strchr(s,',')+1);        
    }    
    return true;
}

bool bfs(vector<int> & ans) {
    queue<Node *> q;
    ans.clear();
    q.push(root);
    while(!q.empty()) {
        Node * u = q.front();
        q.pop();
        if(!u->have_value) return false;
        ans.push_back(u->v);
        if(u->left!=NULL) q.push(u->left);
        if(u->right!=NULL) q.push(u->right);
    }
    return true;
}

int main() {
    while(read_input()) {
        if(failed == true) {
            printf("-1
");
            continue;
        }
        vector<int> ans;
        if(bfs(ans)==false) {
            printf("-1
");
            continue;
        }    
        else {
            for(auto i : ans) {
                cout << i << " ";
            }
            cout << endl;
        }
    }    
    return 0;    
}

View Code

　　思考：自己的代码能力还是差，昨天的CF还没有补题吧孩子，然后就是好好搞ACM吧，这个东西对自己以后肯定是有好处的啊