已知层次序列及结点的度，求树的孩子-兄弟链表的时间复杂度

对于这个问题，可以使用递归的方法来实现孩子-兄弟链表。具体地，可以从根节点开始递归地构建该树的孩子-兄弟链表。

时间复杂度取决于树的大小和结构，对于一棵n个结点的树，最坏的情况下需要遍历所有的结点，因此时间复杂度为O(n)。

但是在实际情况中，由于树的结构和特性的多样性，该算法的时间复杂度可能会有所波动，需要具体问题具体分析。

相关问题

已知一棵树的由根至叶子结点按层次输入的结点序列及每个结点的度，试写出构造此树的孩子-兄弟链表的c语言算法

假设输入的结点序列为nodeList，每个结点的度为degreeList，孩子-兄弟链表为treeList，算法如下：

#include <stdio.h>
#include <stdlib.h>

#define MAX_NODE_NUM 100 // 最大结点数

typedef struct TreeNode {
    int data;
    struct TreeNode *firstChild; // 第一个孩子结点
    struct TreeNode *nextSibling; // 下一个兄弟结点
} TreeNode;

TreeNode *createTree(int nodeList[], int degreeList[], int n) {
    TreeNode *treeList[MAX_NODE_NUM];
    int i, j;
    for (i = 0; i < n; i++) {
        TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
        node->data = nodeList[i];
        node->firstChild = NULL;
        node->nextSibling = NULL;
        treeList[i] = node;
    }
    TreeNode *root = treeList[0];
    TreeNode *queue[MAX_NODE_NUM];
    int front = 0, rear = 0;
    queue[rear++] = root;
    for (i = 1; i < n;) {
        TreeNode *parent = queue[front];
        front++;
        for (j = 0; j < degreeList[i]; j++) {
            parent->firstChild = treeList[i];
            i++;
            treeList[i - 1]->nextSibling = treeList[i];
            queue[rear++] = treeList[i - 1];
        }
    }
    return root;
}

void printTree(TreeNode *root) {
    if (root != NULL) {
        printf("%d ", root->data);
        printTree(root->firstChild);
        printTree(root->nextSibling);
    }
}

int main() {
    int nodeList[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int degreeList[] = {2, 3, 0, 2, 0, 0, 1, 0, 0, 0};
    int n = sizeof(nodeList) / sizeof(int);
    TreeNode *root = createTree(nodeList, degreeList, n);
    printTree(root);
    return 0;
}

算法思路：

1. 根据结点序列和度数数组创建结点数组treeList，并初始化每个结点的firstChild和nextSibling指针为NULL。
2. 将第一个结点作为根节点，并加入队列中。
3. 从第二个结点开始，按输入顺序一次遍历每个结点，对于每个结点，将其作为其父节点的孩子结点，并将其加入队列中，直到所有结点都被遍历完毕。
4. 返回根节点。

时间复杂度为O(n)，空间复杂度为O(n)。

(gcc)7-1 两个有序链表序列的合并 (20 分) 已知两个非降序链表序列s1与s2,设计函

设计一个函数mergeList，用于合并两个非降序链表序列s1和s2。

算法步骤如下：
1. 创建一个新的链表头结点newHead。
2. 分别用两个指针p1和p2指向s1和s2的头结点。
3. 如果p1和p2都不为空，则比较p1和p2指向的节点的值，将较小的节点加入新链表，并将较小节点所在链表的指针后移一位。
4. 如果p1为空但p2不为空，则将p2所指节点加入新链表，并将p2后移一位。
5. 如果p2为空但p1不为空，则将p1所指节点加入新链表，并将p1后移一位。
6. 重复步骤3至5，直到p1和p2都为空。
7. 返回新链表的头结点newHead。

该算法的时间复杂度为O(n)，其中n为两个链表的总节点数。

图示示例：
假设s1链表为：1 -> 3 -> 5 -> 7 -> null
s2链表为：2 -> 4 -> 6 -> 8 -> null

执行mergeList(s1, s2)的结果为：
newHead -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null

注意：以上是非降序链表的合并，即节点的值按照从小到大的顺序排列。如果是非升序链表（即节点的值按照从大到小的顺序排列），只需要在步骤3中比较大小时改为找到较大的节点即可。