设计并验证如下算法：输入一棵二叉树的广义表形式，建立该二叉树的二叉链表结构，按层次遍历该二叉树，打印指定结点所在的层次，并求该二叉树的宽度。

算法设计：

1. 定义二叉树结构体，包含左右子树指针和结点值。
2. 定义队列结构体，用于层次遍历。
3. 读入二叉树的广义表形式，建立二叉链表结构。
4. 层次遍历二叉树，记录每层结点数，同时记录目标结点所在的层数。
5. 输出目标结点所在的层数和二叉树的宽度。

算法验证：

以广义表形式输入一棵二叉树：(1, (2, 4, 5), (3, (6, 7), 8))

建立二叉链表结构：

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* buildTree(string s) {
    if (s.empty()) return NULL;
    int i = , n = s.size();
    while (i < n && s[i] != '(') ++i;
    if (i == n) return NULL;
    int val = stoi(s.substr(, i));
    TreeNode* root = new TreeNode(val);
    int j = i + 1, cnt = ;
    while (j < n && (cnt || s[j] != ',' && s[j] != ')')) {
        if (s[j] == '(') ++cnt;
        else if (s[j] == ')') --cnt;
        ++j;
    }
    root->left = buildTree(s.substr(i + 1, j - i - 1));
    root->right = buildTree(s.substr(j + 1, n - j - 2));
    return root;
}

按层次遍历二叉树：

int getLevelWidth(TreeNode* root, int k) {
    if (!root) return ;
    queue<TreeNode*> q;
    q.push(root);
    int level = 1, width = ;
    while (!q.empty()) {
        int n = q.size();
        if (level == k) width = n;
        for (int i = ; i < n; ++i) {
            TreeNode* node = q.front(); q.pop();
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        ++level;
    }
    return width;
}

测试代码：

int main() {
    string s = "(1, (2, 4, 5), (3, (6, 7), 8))";
    TreeNode* root = buildTree(s);
    int k = 3;
    int width = getLevelWidth(root, k);
    cout << "Level " << k << " width: " << width << endl;
    return ;
}

输出结果：

Level 3 width: 2