# UVA 00122 - Trees on the level
## 题目
{%preview https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=58 %}

:::success
解题状态：Accepted
:::
:::info
!!! 本代码仅供学习与交流使用，转载请注明出处。
:::
## 原生c++代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

struct Node
{
    int val;
    string path;
    Node *left;
    Node *right;
};

struct cmp
{
    bool operator()(Node a, Node b)
    {
        return a.path.length() > b.path.length();
    }
};

stringstream ss;
priority_queue<Node, vector<Node>, cmp> heap;
Node root;

Node processInput(string input)
{
    ss.clear();
    input = input.substr(1, input.length() - 2);
    string s_val;
    string path;
    ss.str(input);
    getline(ss, s_val, ',');
    getline(ss, path);
    Node n = {stoi(s_val), path, nullptr, nullptr};
    return n;
}

void clearQueue()
{
    while (!heap.empty())
        heap.pop();
}

void printVals()
{
    queue<Node *> q;
    q.push(&root);
    bool isFirst = true;
    while (!q.empty())
    {
        Node *curr = q.front();
        q.pop();
        if (!isFirst)
            cout << ' ';
        isFirst = false;
        cout << curr->val;
        if (curr->left != nullptr)
        {
            q.push(curr->left);
        }
        if (curr->right != nullptr)
        {
            q.push(curr->right);
        }
    }
    cout << endl;
}

bool processNext()
{ // true->process successfully.
    root = heap.top();
    heap.pop();
    if (root.path != "")
        return false;
    while (!heap.empty())
    {
        Node node = heap.top();
        Node *curr = &root;
        heap.pop();
        string path = node.path;
        char last = path[path.length() - 1];
        for (int i = 0; i < path.length() - 1; i++)
        {
            if (path[i] == 'L')
            {
                if (curr->left == nullptr)
                    return false;
                curr = curr->left;
            }
            else
            {
                if (curr->right == nullptr)
                    return false;
                curr = curr->right;
            }
        }
        if (last == 'L')
        {
            if (curr->left != nullptr)
            {
                return false;
            }
            curr->left = new Node(node);
        }
        else
        {
            if (curr->right != nullptr)
            {
                return false;
            }
            curr->right = new Node(node);
        }
    }
    return true;
}

int main()
{
    string cmd;
    while (cin >> cmd)
    {
        if (cmd == "()")
        {
            bool succ = processNext();
            if (succ)
            {
                printVals();
            }
            else
            {
                cout << "not complete" << endl;
            }
            clearQueue();
            continue;
        }
        heap.push(processInput(cmd));
    }
    return 0;
}

/*
(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()
*/

## GPT-4.1 生成注释c++代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

// 定义树的节点结构体
struct Node
{
    int val;        // 节点的值
    string path;    // 从根节点到该节点的路径（由L和R组成）
    Node *left;     // 左子节点指针
    Node *right;    // 右子节点指针
};

// 优先队列的比较器，按路径长度升序排列
struct cmp
{
    bool operator()(Node a, Node b)
    {
        return a.path.length() > b.path.length();
    }
};

stringstream ss; // 用于处理输入字符串
priority_queue<Node, vector<Node>, cmp> heap; // 存储所有节点的优先队列
Node root; // 二叉树的根节点

// 解析输入字符串，生成节点
Node processInput(string input)
{
    ss.clear();
    input = input.substr(1, input.length() - 2); // 去掉括号
    string s_val;
    string path;
    ss.str(input);
    getline(ss, s_val, ','); // 读取节点值
    getline(ss, path);       // 读取路径
    Node n = {stoi(s_val), path, nullptr, nullptr};
    return n;
}

// 清空优先队列
void clearQueue()
{
    while (!heap.empty())
        heap.pop();
}

// 层序遍历并输出二叉树的所有节点值
void printVals()
{
    queue<Node *> q;
    q.push(&root);
    bool isFirst = true;
    while (!q.empty())
    {
        Node *curr = q.front();
        q.pop();
        if (!isFirst)
            cout << ' ';
        isFirst = false;
        cout << curr->val;
        if (curr->left != nullptr)
        {
            q.push(curr->left);
        }
        if (curr->right != nullptr)
        {
            q.push(curr->right);
        }
    }
    cout << endl;
}

// 构建二叉树，检查是否完全指定，返回true表示成功
bool processNext()
{ // true->process successfully.
    root = heap.top();
    heap.pop();
    if (root.path != "")
        return false; // 根节点路径必须为空
    while (!heap.empty())
    {
        Node node = heap.top();
        Node *curr = &root;
        heap.pop();
        string path = node.path;
        char last = path[path.length() - 1];
        // 沿着路径找到父节点
        for (int i = 0; i < path.length() - 1; i++)
        {
            if (path[i] == 'L')
            {
                if (curr->left == nullptr)
                    return false; // 路径中有未指定的父节点
                curr = curr->left;
            }
            else
            {
                if (curr->right == nullptr)
                    return false; // 路径中有未指定的父节点
                curr = curr->right;
            }
        }
        // 插入新节点到对应的左或右子节点
        if (last == 'L')
        {
            if (curr->left != nullptr)
            {
                return false; // 节点重复指定
            }
            curr->left = new Node(node);
        }
        else
        {
            if (curr->right != nullptr)
            {
                return false; // 节点重复指定
            }
            curr->right = new Node(node);
        }
    }
    return true;
}

int main()
{
    string cmd;
    // 逐个读取输入，直到遇到"()"表示一棵树输入结束
    while (cin >> cmd)
    {
        if (cmd == "()")
        {
            bool succ = processNext(); // 构建树并检查完整性
            if (succ)
            {
                printVals(); // 输出层序遍历结果
            }
            else
            {
                cout << "not complete" << endl; // 树不完整
            }
            clearQueue(); // 清空队列，准备下一棵树
            continue;
        }
        heap.push(processInput(cmd)); // 解析并加入优先队列
    }
    return 0;
}

/*
(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()
*/

---

> 日期：2025/05/12