记录编号	616078	评测结果	AAAAAAAAAA
题目名称	1644.树的层次遍历	最终得分	100
用户昵称	张宸汉	是否通过	通过
代码语言	C++	运行时间	0.033 s
提交时间	2026-05-30 12:53:05	内存使用	3.71 MiB

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

const int MAXN = 300;  

// 跳过所有空白字符
void skipSpace()
{
    // 下一个字符不是文件尾  &&  下一个字符是空白符 
    // cin.peek() 从输入流 cin 里预读下一个字符，只看不取
    // EOF 本质是一个整数（一般值为 -1），代表输入结束 
    // isspace 判断一个字符是不是空白字符
    // static_cast<unsigned char>(x) 是 C++ 标准强制类型转换 
    while (cin.peek() != EOF && isspace(static_cast<unsigned char>(cin.peek())))
    {
        // 将这个空白字符删去 
        cin.get();
    }
}

// 读取一个节点
// 成功读到节点返回false，读到结束符()返回true
bool readNode(string pathArr[], int valArr[], int& cnt)
{
    skipSpace();
    if (cin.peek() == EOF)
        return true;

    char c;
    cin.get(c);   // 读 '('

    skipSpace();
    // 遇到结束标记 ()
    if (cin.peek() == ')')
    {
        cin.get(c);
        return true;
    }

    // 读取正整数
    int num = 0;
    while (isdigit(static_cast<unsigned char>(cin.peek())))
    {
        cin.get(c);
        num = num * 10 + c - '0';
    }

    // 跳过逗号
    skipSpace();
    cin.get(c);
    skipSpace();

    // 读取路径字符串
    string path;
    while (cin.peek() != ')' && !isspace(static_cast<unsigned char>(cin.peek())) && cin.peek() != EOF)
    {
        cin.get(c);
        path += c;
    }

    // 跳过右括号及后面空白
    skipSpace();
    while (cin.peek() != ')' && cin.peek() != EOF)
        cin.get(c);
    if (cin.peek() == ')')
        cin.get(c);

    // 存入数组
    pathArr[cnt] = path;
    valArr[cnt] = num;
    cnt++;

    return false;
}

// 检查：是否存在重复路径
bool hasRepeat(string pathArr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (pathArr[i] == pathArr[j])
                return true;
        }
    }
    return false;
}

// 检查：所有节点的祖先路径都存在
bool allAncestorExist(string pathArr[], int n)
{
    // 必须存在根节点（空路径）
    bool hasRoot = false;
    for (int i = 0; i < n; i++)
    {
        if (pathArr[i] == "")
        {
            hasRoot = true;
            break;
        }
    }
    if (!hasRoot)
        return false;

    // 逐个检查每个节点的每一级祖先
    for (int i = 0; i < n; i++)
    {
        string cur = pathArr[i];
        int len = cur.size();
        // 截取前缀作为祖先
        for (int j = 1; j < len; j++)
        {
            string pre = cur.substr(0, j);
            bool find = false;
            for (int k = 0; k < n; k++)
            {
                if (pathArr[k] == pre)
                {
                    find = true;
                    break;
                }
            }
            if (!find)
                return false;
        }
    }
    return true;
}

// 根据路径找对应数值
int getValue(string pathArr[], int valArr[], int n, string s)
{
    for (int i = 0; i < n; i++)
    {
        if (pathArr[i] == s)
            return valArr[i];
    }
    return -1;
}

// 判断路径是否存在
bool isExist(string pathArr[], int n, string s)
{
    for (int i = 0; i < n; i++)
    {
        if (pathArr[i] == s)
            return true;
    }
    return false;
}

// 层序遍历输出
void levelOrder(string pathArr[], int valArr[], int n)
{
    queue<string> q;
    q.push("");
    bool first = true;

    while (!q.empty())
    {
        string now = q.front();
        q.pop();

        if (!first)
            cout << " ";
        first = false;
        cout << getValue(pathArr, valArr, n, now);

        string left = now + "L";
        string right = now + "R";
        if (isExist(pathArr, n, left))
            q.push(left);
        if (isExist(pathArr, n, right))
            q.push(right);
    }
    cout << endl;
}

int main()
{
    freopen("vlevel.in", "r", stdin);
    freopen("vlevel.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);

    while (true)
    {
        string path[MAXN];
        int val[MAXN];
        int total = 0;

        // 读取本组所有节点，直到 ()
        while (!readNode(path, val, total));

        // 文件结束，退出
        if (cin.eof())
            break;

        // 合法性校验
        bool repeat = hasRepeat(path, total);
        bool ancestorOk = allAncestorExist(path, total);

        if (!repeat && ancestorOk)
        {
            levelOrder(path, val, total);
        }
        else
        {
            cout << "not complete" << endl;
        }
    }
    return 0;
}