3G期末考核题解

一、144.二叉树的前序遍历

• 这是一道经典的二叉树前序遍历，我们用两种方法来解决。

1. 递归法：

• 树的中序遍历口诀：根左右

int* preOrder(struct TreeNode* root, int* arr, int* size) { if (root == NULL) { return NULL; } arr[(*size)++] = root->val; preOrder(root->left, arr, size); preOrder(root->right, arr, size); return arr; } int* preorderTraversal(struct TreeNode* root, int* returnSize) { int sz = 0; int* arr = (int*)malloc(sizeof(int) * 100); preOrder(root, arr, &sz); *returnSize = sz; return arr; }

2. 迭代法：

• 树的中序遍历口诀：根左右
• 迭代法，需要需要借助栈来实现操作先后操作。
• 利用栈的操作原理，先进后出的原理。
• 优先先将右子结点放到栈中，左子结点后放。

int* preorderTraversal(struct TreeNode* root, int* returnSize) { //树中节点数目在范围 [0, 100] 内 *returnSize = 0; int *returnNum = (int *)malloc(sizeof(int)*101); if(root==NULL) { return returnNum; } struct TreeNode* stack[101]; struct TreeNode* nodeIt; int top = 0; stack[top] = root; top++; //先序遍历根左右 while(top > 0) { top--; nodeIt = stack[top]; //判断根左右结点关系 returnNum[ *returnSize] = nodeIt->val; *returnSize = *returnSize + 1; if(nodeIt->right != NULL) { stack[top] = nodeIt->right; top++; } if(nodeIt->left != NULL) { stack[top] = nodeIt->left; top++; } } return returnNum; }

二、LCR 089 打家劫舍

• 这是一道经典动态规划问题。

思路：

1. 定义 dp [i] 表示抢劫到第 i 间房屋的最大金额，核心是对每间房屋做 “抢” 或 “不抢” 的选择：抢则金额为 dp [i-2]+nums [i]，不抢则为 dp [i-1]，取两者最大值作为 dp [i]。

2. 先处理 1 间、2 间房屋的边界情况，再从第 3 间开始递推计算，最终 dp 数组最后一个值即为能抢劫的最大金额。

int rob(int* nums, int numsSize){ //只有1间房屋，直接返回该房屋金额 if (numsSize == 1){ return nums[0]; } //dp[i]表示抢劫到第i间房屋时的最大金额 int dp[numsSize]; //初始化dp数组所有元素为0 memset(dp,0,numsSize); //第0间房屋的最大金额就是自身 dp[0] = nums[0]; //前2间房屋选金额更大的 dp[1] = (nums[0] < nums[1] ? nums[1] : nums[0]); //从第2间房屋开始，递推计算每间的最大金额 for(int i = 2; i < numsSize; i++){ //状态转移：选「不抢第i间」或「抢第i间」的最大值 dp[i] = (dp[i-1] > (dp[i-2] + nums[i]) ? dp[i-1] : (dp[i-2] + nums[i])); } //最后一间房屋的dp值就是全局最大金额 return dp[numsSize-1]; }

三、23.合并K个升序链表

思路：

1. 先遍历所有待合并的链表，将所有节点的值提取到数组中，统一存储。

2. 对存储值的数组进行选择排序，得到升序排列的数值序列。

3. 基于排序后的数组逐个创建节点，拼接成新的有序链表，完成 k 个链表的合并。

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){ struct ListNode *head = NULL, *tail = NULL; int nums[10000] = {0}; //数组存储所有链表节点的值，用于后续排序 int i = 0, j = 0, k = 0, min = 0, swap = 0; //遍历所有链表，将所有节点的值依次存入nums数组，k记录总节点数 for(; i<listsSize; i++){ while(lists[i]){ nums[k++] = lists[i]->val; lists[i] = lists[i]->next; } } //对nums数组进行简单选择排序，确保值按升序排列 for(i=0; i<k; i++){ min = i; //初始化最小值索引为当前位置 for(j=i+1; j<k; j++){ if(nums[j] < nums[min]){ min = j; //更新最小值索引 } } //交换当前位置与最小值位置的元素 if(min != i){ swap = nums[i]; nums[i] = nums[min]; nums[min] = swap; } } //遍历排序后的数组，逐个创建节点并拼接成新的有序链表 for(i=0; i<k; i++){ if(!head){ //初始化链表头节点 struct ListNode *p = malloc(sizeof(struct ListNode)); head = p; tail = p; p->val = nums[i]; p->next = NULL; } else{ //拼接后续节点，维护尾指针 struct ListNode *p = malloc(sizeof(struct ListNode)); p->val = nums[i]; p->next = NULL; tail->next = p; tail = p; } } return head; //返回合并后的有序链表头节点 }