手机和电脑同步的进销存软件_福田公司成立时间_兰州网络seo公司_北京百度推广seo

文章目录

31.K个一组翻转链表
- 题目描述
- 思路
- code
32.随机链表的复制
- 题目描述
- 思路一：哈希+递归
- code
- 思路二：插入法（不用哈希）
- code
33.排序链表
- 题目描述
- 思路一：快排
- code
- 思路二：归并排序
- code
34.合并K个升序链表
- 题目描述
- 思路一：利用数组排序
- code
- 思路二：两两链表进行归并
- code
- 思路三：分治优化
- code
35.LRU缓存
- 题目描述
- 思路：哈希表+双向链表
- code
36.二叉树的中序遍历
- 题目描述
- 思路一：递归算法
- code
- 思路二：迭代法
- code
37.二叉树的最大深度
- 题目描述
- 思路：递归
- code
38.翻转二叉树
- 题目描述
- 思路：递归
- code
39.对称二叉树
- 题目描述
- 思路：递归
- code
40.二叉树的直径
- 题目描述
- 思路：递归
- code

31.K个一组翻转链表

题目描述

25. K 个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

提示：

链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

**进阶：**你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

思路

分段翻转链表：
- 将链表分为若干组，每组 k 个节点。
- 对每一组节点进行翻转。
- 如果最后一组节点不足 k 个，则不翻转。
翻转链表的实现：
- 使用指针操作，翻转指定范围内的链表。
连接各组链表：
- 将翻转后的各组链表连接起来。

code

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/// 翻转链表的辅助函数
struct ListNode* reverse(struct ListNode* head, struct ListNode* tail) {struct ListNode* pre = tail->next; // 翻转后的链表尾部指向 tail->nextstruct ListNode* cur = head;while (pre != tail) {struct ListNode* temp = cur->next;cur->next = pre;pre = cur;cur = temp;}return tail; // 返回翻转后的链表头节点
}struct ListNode* reverseKGroup(struct ListNode* head, int k) {// 创建虚拟头节点，简化操作struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));dummy->next = head;struct ListNode* pre = dummy; // pre 指向每组翻转前的第一个节点的前一个节点while (head) {// 找到每组的尾节点struct ListNode* tail = pre;for (int i = 0; i < k; i++) {tail = tail->next;if (!tail) {// 如果剩余节点不足 k 个，直接返回结果return dummy->next;}}// 保存下一组的头节点struct ListNode* nextGroup = tail->next;// 翻转当前组struct ListNode* newHead = reverse(head, tail);// 将翻转后的组连接到链表中pre->next = newHead;head->next = nextGroup;// 更新 pre 和 headpre = head;head = nextGroup;}// 返回新链表的头节点（跳过虚拟头节点）return dummy->next;
}

32.随机链表的复制

题目描述

138. 随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码只接受原链表的头节点 head 作为传入参数。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

提示：

0 <= n <= 1000
-104 <= Node.val <= 104
Node.random 为 null 或指向链表中的节点。

思路一：哈希+递归

哈希表缓存：
- 使用哈希表缓存已经复制的节点，避免重复复制。
- 哈希表的键是原链表的节点，值是新链表的节点。
递归复制链表：
- 如果当前节点为空，直接返回 NULL。
- 在哈希表中查找当前节点是否已经复制过：
  - 如果已经复制过，直接返回缓存的新节点。
  - 如果未复制过，创建新节点，并将其存入哈希表。
- 递归复制 next 和 random 指针。

code

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/// 定义哈希表结构
struct HashTable {struct Node* key; // 原链表的节点struct Node* val; // 新链表的节点UT_hash_handle hh; // uthash 宏，用于哈希表操作
};// 全局哈希表，用于缓存已复制的节点
struct HashTable* cachedNode = NULL;// 递归复制链表
struct Node* deepCopy(struct Node* head) {if (head == NULL) return NULL; // 如果原链表为空，直接返回 NULL// 在哈希表中查找当前节点是否已经复制过struct HashTable* temp;HASH_FIND_PTR(cachedNode, &head, temp);if (temp == NULL) {// 如果当前节点未复制过，创建新节点struct Node* headNew = malloc(sizeof(struct Node));headNew->val = head->val; // 复制节点的值// 将原节点和新节点存入哈希表temp = malloc(sizeof(struct HashTable));temp->key = head;temp->val = headNew;HASH_ADD_PTR(cachedNode, key, temp);// 递归复制 next 和 random 指针headNew->next = deepCopy(head->next);headNew->random = deepCopy(head->random);}// 返回新链表的节点return temp->val;
}// 复制带随机指针的链表
struct Node* copyRandomList(struct Node* head) {cachedNode = NULL; // 初始化哈希表return deepCopy(head); // 调用递归函数复制链表
}

思路二：插入法（不用哈希）

第一次遍历：插入新节点：
- 遍历原链表，在每个节点后面插入一个新节点。
- 新节点的 val 与原节点相同，next 指向原节点的下一个节点，random 暂时复制原节点的 random 指针。
- 例如，原链表为 A -> B -> C，插入后变为 A -> A' -> B -> B' -> C -> C'。
第二次遍历：设置新节点的 random 指针：
- 遍历链表，设置新节点的 random 指针。
- 如果原节点的 random 指向某个节点，那么新节点的 random 应该指向原节点 random 的下一个节点（即新链表中对应的节点）。
- 例如，如果原节点 A 的 random 指向 C，那么新节点 A' 的 random 应该指向 C'。
第三次遍历：分离原链表和新链表：
- 遍历链表，将原链表和新链表分离。
- 恢复原链表的 next 指针，同时设置新链表的 next 指针。
- 例如，将 A -> A' -> B -> B' -> C -> C' 分离为 A -> B -> C 和 A' -> B' -> C'。

code

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {if (head == NULL) {return NULL; // 如果原链表为空，直接返回 NULL}// 第一次遍历：在原链表的每个节点后面插入新节点for (struct Node* node = head; node != NULL; node = node->next->next) {struct Node* t = malloc(sizeof(struct Node)); // 创建新节点t->val = node->val; // 复制节点的值t->next = node->next; // 新节点的 next 指向原节点的下一个节点t->random = node->random; // 暂时复制 random 指针node->next = t; // 将新节点插入到原节点后面}// 第二次遍历：设置新节点的 random 指针for (struct Node* node = head; node != NULL; node = node->next->next) {struct Node* t = node->next; // 新节点if (node->random) {t->random = node->random->next; // 新节点的 random 指向原节点 random 的下一个节点} else {t->random = NULL; // 如果原节点的 random 为 NULL，新节点的 random 也为 NULL}}// 第三次遍历：分离原链表和新链表struct Node* headNew = head->next; // 新链表的头节点for (struct Node* node = head; node != NULL; node = node->next) {struct Node* t = node->next; // 新节点node->next = node->next->next; // 恢复原链表的 next 指针if(node->next){// 设置新链表的 next 指针t->next=t->next->next;}else t->next=NULL;}return headNew; // 返回新链表的头节点
}

33.排序链表

题目描述

148. 排序链表

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

**进阶：**你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

思路一：快排

先将链表中的值复制到数组中，再使用快速排序，最后修改链表中的值。（这样是取巧的方法）

code

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/// 比较函数，用于 qsort
int cmp(const void* a, const void* b) {return *(int*)a - *(int*)b; // 升序排序
}struct ListNode* sortList(struct ListNode* head) {int nums[50000 + 5]; // 定义一个足够大的数组，用于存储链表节点的值int cnt = 0; // 记录链表的节点数量// 第一次遍历：将链表节点的值存入数组struct ListNode* L = head;while (L) {nums[cnt++] = L->val; // 将节点的值存入数组L = L->next; // 移动到下一个节点}// 对数组进行排序qsort(nums, cnt, sizeof(int), cmp);// 第二次遍历：将排序后的值写回链表L = head;for (int i = 0; i < cnt; i++) {L->val = nums[i]; // 将排序后的值写回链表L = L->next; // 移动到下一个节点}return head; // 返回排序后的链表
}

思路二：归并排序

找到链表的中间节点：
- 使用快慢指针找到链表的中间节点，将链表分为两部分。
递归排序：
- 对两部分链表分别递归调用 sortList 进行排序。
合并有序链表：
- 使用 merge 函数合并两个有序链表。

code

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/// 合并两个有序链表
struct ListNode* merge(struct ListNode* l1, struct ListNode* l2) {struct ListNode dummy; // 虚拟头节点struct ListNode* tail = &dummy; // 尾指针while (l1 && l2) {if (l1->val < l2->val) {tail->next = l1;l1 = l1->next;} else {tail->next = l2;l2 = l2->next;}tail = tail->next;}tail->next = l1 ? l1 : l2; // 将剩余部分连接到链表末尾return dummy.next; // 返回合并后的链表头节点
}// 归并排序
struct ListNode* sortList(struct ListNode* head) {if (!head || !head->next) {return head; // 如果链表为空或只有一个节点，直接返回}// 使用快慢指针找到链表的中间节点struct ListNode* slow = head;struct ListNode* fast = head->next;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}// 将链表分为两部分struct ListNode* mid = slow->next;slow->next = NULL;// 递归排序两部分链表struct ListNode* left = sortList(head);struct ListNode* right = sortList(mid);// 合并排序后的链表return merge(left, right);
}

34.合并K个升序链表

题目描述

23. 合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[1->4->5,1->3->4,2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按升序排列
lists[i].length 的总和不超过 10^4

思路一：利用数组排序

将链表的值存储到数组中：
- 遍历所有链表，将每个节点的值存入数组 a。
- 使用变量 cnt 记录所有链表节点的数量。
对数组进行排序：
- 使用 qsort 函数对数组 a 进行升序排序。
构建新链表：
- 创建一个虚拟头节点 head，用于简化链表操作。
- 根据排序后的数组 a，逐个创建新节点并接入链表。
返回结果：
- 返回新链表的头节点（跳过虚拟头节点）。

code

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/// 比较函数，用于 qsort
int cmp(const void* a, const void* b) {return *(int*)a - *(int*)b; // 升序排序
}struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {if (listsSize == 0) return NULL; // 如果链表数组为空，直接返回 NULLint a[10005]; // 定义一个足够大的数组，用于存储所有链表节点的值int cnt = 0; // 记录所有链表节点的数量// 遍历所有链表，将节点的值存入数组for (int i = 0; i < listsSize; i++) {if (lists[i] == NULL) continue; // 如果当前链表为空，跳过struct ListNode* head = lists[i];while (head) {a[cnt++] = head->val; // 将节点的值存入数组head = head->next; // 移动到下一个节点}}// 对数组进行排序qsort(a, cnt, sizeof(int), cmp);// 创建一个虚拟头节点，用于构建新链表struct ListNode* head = malloc(sizeof(struct ListNode));head->next=NULL;struct ListNode* p = head;// 根据排序后的数组构建新链表for (int i = 0; i < cnt; i++) {struct ListNode* t = malloc(sizeof(struct ListNode));t->val = a[i]; // 设置节点的值t->next = NULL; // 设置节点的 next 指针p->next = t; // 将新节点接入链表p = p->next; // 移动指针}return head->next; // 返回新链表的头节点（跳过虚拟头节点）
}

思路二：两两链表进行归并

逐个合并链表：

初始化结果为第一个链表。
逐个将剩余的链表合并到结果中。

code

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/// 合并两个有序链表
struct ListNode* mergeList(struct ListNode* l1, struct ListNode* l2) {struct ListNode* head = malloc(sizeof(struct ListNode)); // 创建虚拟头节点head->next = NULL; // 初始化虚拟头节点的 next 指针struct ListNode* L = head; // 用于遍历新链表的指针// 遍历两个链表，逐个比较节点值while (l1 && l2) {if (l1->val < l2->val) {L->next = l1; // 将 l1 的当前节点接入新链表l1 = l1->next; // 移动 l1 指针} else {L->next = l2; // 将 l2 的当前节点接入新链表l2 = l2->next; // 移动 l2 指针}L = L->next; // 移动新链表指针}// 将剩余部分接入新链表if (l1) L->next = l1;else L->next = l2;return head->next; // 返回新链表的头节点（跳过虚拟头节点）
}// 合并 k 个有序链表
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {if (listsSize == 0) return NULL; // 如果链表数组为空，直接返回 NULLstruct ListNode* head = lists[0]; // 初始化结果为第一个链表// 逐个合并链表for (int i = 1; i < listsSize; i++) {head = mergeList(head, lists[i]); // 将当前链表合并到结果中}return head; // 返回合并后的链表
}

思路三：分治优化

用分治法可以对思路二进行优化

分治法：
- 将 k 个链表分为两半，递归合并每一半。
- 最后将两部分合并为一个链表。

code

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/// 合并两个有序链表
struct ListNode* mergeList(struct ListNode* l1, struct ListNode* l2) {struct ListNode* head = malloc(sizeof(struct ListNode)); // 创建虚拟头节点head->next = NULL; // 初始化虚拟头节点的 next 指针struct ListNode* L = head; // 用于遍历新链表的指针// 遍历两个链表，逐个比较节点值while (l1 && l2) {if (l1->val < l2->val) {L->next = l1; // 将 l1 的当前节点接入新链表l1 = l1->next; // 移动 l1 指针} else {L->next = l2; // 将 l2 的当前节点接入新链表l2 = l2->next; // 移动 l2 指针}L = L->next; // 移动新链表指针}// 将剩余部分接入新链表if (l1) L->next = l1;else L->next = l2;return head->next; // 返回新链表的头节点（跳过虚拟头节点）
}// 分治法合并 k 个有序链表
struct ListNode* mergeKListsHelper(struct ListNode** lists, int left, int right) {if (left == right) return lists[left]; // 如果只有一个链表，直接返回int mid = left + (right - left) / 2; // 计算中间位置struct ListNode* l1 = mergeKListsHelper(lists, left, mid); // 递归合并左半部分struct ListNode* l2 = mergeKListsHelper(lists, mid + 1, right); // 递归合并右半部分return mergeList(l1, l2); // 合并左右两部分
}struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {if (listsSize == 0) return NULL; // 如果链表数组为空，直接返回 NULLreturn mergeKListsHelper(lists, 0, listsSize - 1); // 调用分治法合并链表
}

35.LRU缓存

题目描述

146. LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。

实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

思路：哈希表+双向链表

哈希表用于快速查找节点，双向链表用于维护节点的顺序，确保最近使用的节点始终在链表头部，最久未使用的节点在链表尾部。

本题我还不太会，机试应该不会有代码量这么大的题。

code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 定义双向链表节点结构
typedef struct DLinkedNode {int key;int value;struct DLinkedNode* prev;struct DLinkedNode* next;
} DLinkedNode;// 定义 LRU 缓存结构
typedef struct {int capacity;              // 缓存容量int size;                 // 当前缓存大小DLinkedNode* head;        // 虚拟头节点DLinkedNode* tail;        // 虚拟尾节点DLinkedNode** cache;      // 哈希表，用于快速查找节点
} LRUCache;// 创建新节点
DLinkedNode* createNode(int key, int value) {DLinkedNode* node = (DLinkedNode*)malloc(sizeof(DLinkedNode));node->key = key;node->value = value;node->prev = NULL;node->next = NULL;return node;
}// 初始化 LRU 缓存
LRUCache* lRUCacheCreate(int capacity) {LRUCache* cache = (LRUCache*)malloc(sizeof(LRUCache));cache->capacity = capacity;cache->size = 0;cache->head = createNode(0, 0);  // 虚拟头节点cache->tail = createNode(0, 0);  // 虚拟尾节点cache->head->next = cache->tail;cache->tail->prev = cache->head;cache->cache = (DLinkedNode**)calloc(10000, sizeof(DLinkedNode*));  // 哈希表return cache;
}// 将节点添加到链表头部
void addToHead(LRUCache* obj, DLinkedNode* node) {node->prev = obj->head;node->next = obj->head->next;obj->head->next->prev = node;obj->head->next = node;
}// 移除链表中的节点
void removeNode(DLinkedNode* node) {node->prev->next = node->next;node->next->prev = node->prev;
}// 将节点移动到链表头部
void moveToHead(LRUCache* obj, DLinkedNode* node) {removeNode(node);addToHead(obj, node);
}// 移除链表尾部节点
DLinkedNode* removeTail(LRUCache* obj) {DLinkedNode* node = obj->tail->prev;removeNode(node);return node;
}// 获取缓存中的值
int lRUCacheGet(LRUCache* obj, int key) {if (obj->cache[key] == NULL) {return -1;  // 未找到}DLinkedNode* node = obj->cache[key];moveToHead(obj, node);  // 将节点移动到链表头部return node->value;
}// 插入或更新缓存
void lRUCachePut(LRUCache* obj, int key, int value) {if (obj->cache[key] != NULL) {// 如果 key 已存在，更新 value 并移动到链表头部DLinkedNode* node = obj->cache[key];node->value = value;moveToHead(obj, node);} else {// 如果 key 不存在，创建新节点并插入到链表头部DLinkedNode* node = createNode(key, value);obj->cache[key] = node;addToHead(obj, node);obj->size++;if (obj->size > obj->capacity) {// 如果超出容量，移除链表尾部节点DLinkedNode* removed = removeTail(obj);obj->cache[removed->key] = NULL;free(removed);obj->size--;}}
}// 释放 LRU 缓存
void lRUCacheFree(LRUCache* obj) {DLinkedNode* curr = obj->head->next;while (curr != obj->tail) {DLinkedNode* temp = curr;curr = curr->next;free(temp);}free(obj->head);free(obj->tail);free(obj->cache);free(obj);
}

36.二叉树的中序遍历

题目描述

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的中序遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

思路一：递归算法

中序遍历的顺序：

中序遍历的顺序是：左子树 -> 根节点 -> 右子树。
递归实现：使用递归函数 inorder 实现中序遍历。
存储结果：使用指针 count 记录数组的当前索引。

code

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/// 递归中序遍历
void inorder(struct TreeNode* root, int* ans, int* count) {if (root == NULL) return; // 如果当前节点为空，直接返回inorder(root->left, ans, count); // 递归遍历左子树ans[(*count)++] = root->val; // 将当前节点的值存入数组inorder(root->right, ans, count); // 递归遍历右子树
}// 中序遍历入口函数
int* inorderTraversal(struct TreeNode* root, int* returnSize) {int* ans = malloc(sizeof(int) * 100); // 分配一个足够大的数组，用于存储遍历结果*returnSize = 0; // 初始化返回数组的大小为 0inorder(root, ans, returnSize); // 调用递归函数进行中序遍历return ans; // 返回遍历结果数组
}

思路二：迭代法

使用栈模拟递归：
- 使用栈来模拟递归的过程，避免递归调用栈的开销。
- 栈用于存储待处理的节点。
遍历过程：

从根节点开始，将所有左子节点入栈。
弹出栈顶节点，将其值存入结果数组。
移动到右子节点，重复上述过程。

code

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*//*** Note: The returned array must be malloced, assume caller calls free().*/
int* inorderTraversal(struct TreeNode* root, int* returnSize) {int* ans = malloc(sizeof(int) * 100); // 分配一个足够大的数组，用于存储遍历结果*returnSize = 0; // 初始化返回数组的大小为 0if (root == NULL) return ans; // 如果树为空，直接返回空数组struct TreeNode* st[100]; // 定义一个栈，用于模拟递归过程int top = 0; // 栈顶指针struct TreeNode* node = root; // 当前节点指针// 中序遍历while (top > 0 || node != NULL) {// 将当前节点的所有左子节点入栈while (node != NULL) {st[top++] = node; // 节点入栈node = node->left; // 移动到左子节点}// 弹出栈顶节点node = st[--top];ans[(*returnSize)++] = node->val; // 将节点值存入结果数组// 移动到右子节点node = node->right;}return ans; // 返回遍历结果数组
}

37.二叉树的最大深度

题目描述

104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

输入：root = [1,null,2]
输出：2

提示：

树中节点的数量在 [0, 104] 区间内。
-100 <= Node.val <= 100

思路：递归

递归终止条件：
- 如果当前节点为空（root == NULL），返回深度 0。
递归计算左右子树的深度：
- 递归计算左子树的最大深度 leftDepth。
- 递归计算右子树的最大深度 rightDepth。
返回当前子树的最大深度：
- 当前子树的最大深度为左右子树的最大深度加 1（当前节点的深度）。

code

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/// 辅助函数：返回两个整数中的较大值
int Max(int a, int b) {return a > b ? a : b;
}// 计算二叉树的最大深度
int maxDepth(struct TreeNode* root) {if (root == NULL) return 0; // 如果当前节点为空，深度为 0// 递归计算左子树和右子树的最大深度int leftDepth = maxDepth(root->left);int rightDepth = maxDepth(root->right);// 返回左右子树的最大深度加 1（当前节点的深度）return Max(leftDepth, rightDepth) + 1;
}

38.翻转二叉树

题目描述

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100

思路：递归

递归翻转所有子树

code

struct TreeNode* invertTree(struct TreeNode* root) {if (root == NULL) return NULL;  // 递归终止条件 交换左右子树struct TreeNode* temp = root->left;  root->left = root->right;root->right = temp;invertTree(root->left);  // 递归翻转左子树invertTree(root->right); // 递归翻转右子树return root;
}

39.对称二叉树

题目描述

101. 对称二叉树

给你一个二叉树的根节点 root ，检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

进阶：你可以运用递归和迭代两种方法解决这个问题吗？

思路：递归

递归判断左右子树是否互为对称。

code

bool ismirror(struct TreeNode* root1, struct TreeNode* root2) {if (root1 == NULL && root2 == NULL) return true;  // 两个节点都为空if (root1 == NULL || root2 == NULL) return false; // 一个节点为空，另一个不为空return (root1->val == root2->val) &&              // 当前节点值相等ismirror(root1->left, root2->right) &&    // 递归比较左子树的左节点和右子树的右节点ismirror(root1->right, root2->left);      // 递归比较左子树的右节点和右子树的左节点
}bool isSymmetric(struct TreeNode* root) {if (root == NULL) return true;  // 空树是对称的return ismirror(root->left, root->right);  // 比较左右子树
}

40.二叉树的直径

题目描述

543. 二叉树的直径

给你一棵二叉树的根节点，返回该树的直径。

二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的长度由它们之间边数表示。

示例 1：

输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2：

输入：root = [1,2]
输出：1

提示：

树中节点数目在范围 [1, 104] 内
-100 <= Node.val <= 100

思路：递归

递归计算深度并更新直径：

使用递归函数 dfs 计算二叉树的深度。
在递归过程中，更新直径的最大值。

code

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/// 递归计算深度并更新直径
int dfs(struct TreeNode* root, int* diameter) {if (root == NULL) return 0; // 如果当前节点为空，深度为 0// 递归计算左右子树的深度int leftDepth = dfs(root->left, diameter);int rightDepth = dfs(root->right, diameter);// 更新直径*diameter = fmax(*diameter, leftDepth + rightDepth);// 返回当前子树的最大深度return fmax(leftDepth, rightDepth) + 1;
}// 计算二叉树的直径
int diameterOfBinaryTree(struct TreeNode* root) {int diameter = 0; // 初始化直径为 0dfs(root, &diameter); // 调用递归函数计算深度并更新直径return diameter; // 返回直径
}

手机和电脑同步的进销存软件_福田公司成立时间_兰州网络seo公司_北京百度推广seo

文章目录

31.K个一组翻转链表

题目描述

思路

code

32.随机链表的复制

题目描述

思路一：哈希+递归

code

思路二：插入法（不用哈希）

code

33.排序链表

题目描述

思路一：快排

code

思路二：归并排序

code

34.合并K个升序链表

题目描述

思路一：利用数组排序

code

思路二：两两链表进行归并

code

思路三：分治优化

code

35.LRU缓存

题目描述

思路：哈希表+双向链表

code

36.二叉树的中序遍历

题目描述

思路一：递归算法

code

思路二：迭代法

code

37.二叉树的最大深度

题目描述

思路：递归

code

38.翻转二叉树

题目描述

思路：递归

code

39.对称二叉树

题目描述

思路：递归

code

40.二叉树的直径

题目描述

思路：递归

code

最新新闻

热搜词