力扣面试题 31 - 特定深度节点链表 C语言解法

题目：

给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。

示例：

输入：[1,2,3,4,5,null,7,8]1/  \ 2    3/ \    \ 4   5    7/8输出：[[1],[2,3],[4,5,7],[8]]

思路：

1. 队列辅助层次遍历：使用一个队列来处理树的层次遍历，将每一层节点逐一入队和出队。
2. 链表构建：对于每一层，创建一个单独的链表，逐一添加节点到链表末尾。
3. 结果存储：将每层的链表存入结果数组中，并记录链表数量。

代码如下：（不得不说，C语言真的是麻烦死了）

不懂的可以在评论区问我噢~

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*/
// Queue node definition for BFS
struct QueueNode {struct TreeNode *treeNode;struct QueueNode *next;
};// Queue structure for BFS
struct Queue {struct QueueNode *front;struct QueueNode *rear;
};// Function to create a new queue
struct Queue* createQueue() {struct Queue *queue = (struct Queue*)malloc(sizeof(struct Queue));queue->front = queue->rear = NULL;return queue;
}// Enqueue operation
void enqueue(struct Queue *queue, struct TreeNode *treeNode) {struct QueueNode *newNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));newNode->treeNode = treeNode;newNode->next = NULL;if (queue->rear) {queue->rear->next = newNode;}queue->rear = newNode;if (!queue->front) {queue->front = newNode;}
}// Dequeue operation
struct TreeNode* dequeue(struct Queue *queue) {if (!queue->front) return NULL;struct QueueNode *temp = queue->front;struct TreeNode *treeNode = temp->treeNode;queue->front = queue->front->next;if (!queue->front) {queue->rear = NULL;}free(temp);return treeNode;
}// Check if the queue is empty
int isQueueEmpty(struct Queue *queue) {return queue->front == NULL;
}// Main function
struct ListNode** listOfDepth(struct TreeNode* tree, int* returnSize) {if (!tree) {*returnSize = 0;return NULL;}// Allocate memory for result arraystruct ListNode** result = (struct ListNode**)malloc(1000 * sizeof(struct ListNode*)); // Assuming max depth is 1000*returnSize = 0;struct Queue *queue = createQueue();enqueue(queue, tree);while (!isQueueEmpty(queue)) {int levelSize = 0;struct ListNode *levelHead = NULL, *levelTail = NULL;struct Queue *tempQueue = createQueue();// Process all nodes at the current levelwhile (!isQueueEmpty(queue)) {struct TreeNode *currentNode = dequeue(queue);struct ListNode *newListNode = (struct ListNode*)malloc(sizeof(struct ListNode));newListNode->val = currentNode->val;newListNode->next = NULL;if (!levelHead) {levelHead = newListNode;} else {levelTail->next = newListNode;}levelTail = newListNode;levelSize++;if (currentNode->left) enqueue(tempQueue, currentNode->left);if (currentNode->right) enqueue(tempQueue, currentNode->right);}// Append the level's linked list to the resultresult[*returnSize] = levelHead;(*returnSize)++;// Swap queuesstruct Queue *swapTemp = queue;queue = tempQueue;free(swapTemp);}// Cleanupfree(queue);return result;
}