【数据结构与算法】根据层序序列重构二叉树

#include <bits/stdc++.h>
using namespace std;

struct Node {
    string val;
    Node *left, *right;
    Node(string v) : val(v), left(nullptr), right(nullptr) {}
};

// 根据层序序列重建二叉树
Node* buildTree(vector<string>& level) {
    if (level.empty() || level[0] == "#") return nullptr;
    Node* root = new Node(level[0]);
    queue<Node*> q;
    q.push(root);
    int i = 1;
    while (!q.empty() && i < level.size()) {
        Node* cur = q.front(); q.pop();
        if (i < level.size() && level[i] != "#") {
            cur->left = new Node(level[i]);
            q.push(cur->left);
        }
        i++;
        if (i < level.size() && level[i] != "#") {
            cur->right = new Node(level[i]);
            q.push(cur->right);
        }
        i++;
    }
    return root;
}

// 层序遍历输出
void levelorder(Node* root) {
    if (!root) return;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* cur = q.front(); q.pop();
        cout << cur->val << "\n";
        if (cur->left) q.push(cur->left);
        if (cur->right) q.push(cur->right);
    }
}

int main() {
    int n;
    cin >> n;
    vector<string> level(n);
    for (int i = 0; i < n; i++) cin >> level[i];
    Node* root = buildTree(level);
    levelorder(root);
    return 0;
}