M07161: 森林的带度数层次序列存储

tree, http://cs101.openjudge.cn/practice/07161/

思路：根据带度数的层次序列恢复树，再进行后根遍历输出

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct Node {
    char val;
    vector<Node*> children;
    Node(char c) : val(c) {}
};


void postorder(Node* root) {
    if (!root) return;
    for (int i = 0; i < (int)root->children.size(); ++i)
        postorder(root->children[i]);
    cout << root->val << " ";
}


Node* buildTree() {
    vector<char> vals;
    vector<int> degs;
    char c;
    int d;


    while (cin >> c >> d) {
        vals.push_back(c);
        degs.push_back(d);
        if (cin.peek() == '\n') break; 
    }

    if (vals.empty()) return nullptr;

    queue<Node*> q;
    Node* root = new Node(vals[0]);
    q.push(root);

    int idx = 1;
    for (int i = 0; !q.empty() && idx < (int)vals.size(); ++i) {
        Node* parent = q.front();
        q.pop();

        int cnt = degs[i]; 
        for (int j = 0; j < cnt && idx < (int)vals.size(); ++j) {
            Node* child = new Node(vals[idx]);
            parent->children.push_back(child);
            q.push(child);
            idx++;
        }
    }
    return root;
}

int main() {
    int n;
    cin >> n;

    vector<Node*> forest;
    forest.reserve(n);


    for (int i = 0; i < n; ++i) {
        Node* t = buildTree();
        forest.push_back(t);
    }


    for (int i = 0; i < n; ++i)
        postorder(forest[i]);

    cout << endl;
    return 0;
}

思路：读取每个测试用例的节点信息，利用队列构建树结构，然后进行后序遍历输出所有节点值。

#include <iostream>
#include <vector>
#include <queue>
#include <sstream>
#include <string>

using namespace std;
struct Node {
    char val;
    vector<Node*> children;
    Node(char c) : val(c) {}
};
vector<string> split(const string &s) {
    vector<string> res;
    stringstream ss(s);
    string token;
    while (ss >> token) {
        res.push_back(token);
    }
    return res;
}
Node* buildTree(const vector<pair<char, int>> &nodes) {
    if (nodes.empty()) return nullptr;
    Node* root = new Node(nodes[0].first);
    queue<pair<Node*, int>> q; 
    q.push({root, nodes[0].second});
    
    int i = 1;
    while (i < nodes.size() && !q.empty()) {
        auto [parent, need] = q.front();
        q.pop();
        for (int j = 0; j < need && i < nodes.size(); ++j) {
            char val = nodes[i].first;
            int degree = nodes[i].second;
            Node* child = new Node(val);
            parent->children.push_back(child);
            if (degree > 0) {
                q.push({child, degree}); 
            }
            ++i;
        }
    }
    return root;
}
void postOrder(Node* node, string &s) {
    if (!node) return;
    for (Node* child : node->children) {
        postOrder(child, s);
    }
    s += node->val;
    s += " ";
}

int main() {
    int n;
    cin >> n;
    cin.ignore(); 
    string result;
    for (int i = 0; i < n; ++i) {
        string line;
        getline(cin, line);
        vector<string> tokens = split(line);
        vector<pair<char, int>> nodes;
        for (int j = 0; j + 1 < tokens.size(); j += 2) {
            char c = tokens[j][0];
            int d = stoi(tokens[j + 1]);
            nodes.emplace_back(c, d);
        }
        Node* root = buildTree(nodes);
        postOrder(root, result);
    }
    if (!result.empty()) {
        result.pop_back();
    }
    cout << result << endl;
    
    return 0;
}