网站建设的电话回访,免费行情软件app网站下载大全,最受欢迎的十大培训课程,广州做网站找酷爱网络题目#xff1a;
给定一棵二叉树#xff0c;设计一个算法#xff0c;创建含有某一深度上所有节点的链表#xff08;比如#xff0c;若一棵树的深度为 D#xff0c;则会创建出 D 个链表#xff09;。返回一个包含所有深度的链表的数组。 示例#xff1a;
输入#xf…题目
给定一棵二叉树设计一个算法创建含有某一深度上所有节点的链表比如若一棵树的深度为 D则会创建出 D 个链表。返回一个包含所有深度的链表的数组。 示例
输入[1,2,3,4,5,null,7,8]1/ \ 2 3/ \ \ 4 5 7/8输出[[1],[2,3],[4,5,7],[8]]
思路
队列辅助层次遍历使用一个队列来处理树的层次遍历将每一层节点逐一入队和出队。链表构建对于每一层创建一个单独的链表逐一添加节点到链表末尾。结果存储将每层的链表存入结果数组中并记录链表数量。
代码如下不得不说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 levels linked list to the resultresult[*returnSize] levelHead;(*returnSize);// Swap queuesstruct Queue *swapTemp queue;queue tempQueue;free(swapTemp);}// Cleanupfree(queue);return result;
}
