《LeetCode 热题 100》整整 100 题量大管饱题解套餐中

技术文档

Q34、合并 K 个升序链表

1、题目描述

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

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

示例 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

2、解题思路

方法一：顺序合并

逐个合并：依次将每个链表与当前结果链表合并
合并两个链表：使用合并两个有序链表的算法

方法二：分治合并

分治思想：将k个链表分成两部分，分别合并后再合并两个结果
递归合并：递归地将链表数组分成更小的部分进行合并

方法三：最小堆/优先队列

优先队列：使用优先队列维护当前所有链表的最小元素
逐个取出：每次取出最小元素加入结果链表，并将其下一个元素放入队列

3、代码实现

C++

// 方法1: 顺序合并class Solution {public: ListNode* mergeKLists(vector& lists) { ListNode* result = nullptr; // 逐个合并链表 for (ListNode* list : lists) { result = mergeTwoLists(result, list); } return result; }private: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* cur = &dummy; while (l1 && l2) { if (l1->val val) { cur->next = l1; l1 = l1->next; } else { cur->next = l2; l2 = l2->next; } cur = cur->next; } cur->next = l1 ? l1 : l2; return dummy.next; }};

// 方法2: 分治合并class Solution {public: ListNode* mergeKLists(vector& lists) { return merge(lists, 0, lists.size() - 1); }private: ListNode* merge(vector& lists, int left, int right) { if (left > right) { return nullptr; } if (left == right) { return lists[left]; } int mid = left + (right - left) / 2; ListNode* l1 = merge(lists, left, mid); ListNode* l2 = merge(lists, mid + 1, right); return mergeTwoLists(l1, l2); } ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* cur = &dummy; while (l1 && l2) { if (l1->val val) { cur->next = l1; l1 = l1->next; } else { cur->next = l2; l2 = l2->next; } cur = cur->next; } cur->next = l1 ? l1 : l2; return dummy.next; }};

// 方法3: 最小堆/优先队列class Solution {public: struct Compare { bool operator()(const ListNode* a, const ListNode* b) { return a->val > b->val; } }; ListNode* mergeKLists(vector& lists) { priority_queue<ListNode*, vector, Compare> pq; // 初始化优先队列, 放入每个链表的头节点 for (ListNode* list : lists) { if (list) { pq.push(list); } } ListNode dummy(0); ListNode* cur = &dummy; while (!pq.empty()) { ListNode* minNode = pq.top(); pq.pop(); cur->next = minNode; cur = cur->next; if (minNode->next) { pq.push(minNode->next); } } return dummy.next; }};

Java

class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val); // 初始化优先队列 for (ListNode node : lists) { if (node != null) { pq.add(node); } } ListNode dummy = new ListNode(0); ListNode cur = dummy; while (!pq.isEmpty()) { ListNode minNode = pq.poll(); cur.next = minNode; cur = cur.next; if (minNode.next != null) { pq.add(minNode.next); } } return dummy.next; }}

Python

class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: heap = [] # 初始化堆 for i, node in enumerate(lists): if node: heapq.heappush(heap, (node.val, i, node)) dummy = ListNode(0) cur = dummy while heap: val, idx, node = heapq.heappop(heap) cur.next = node cur = cur.next if node.next: heapq.heappush(heap, (node.next.val, idx, node.next)) return dummy.next

4、复杂度分析

方法时间复杂度空间复杂度顺序合并 O(k^2 * n) O(1) 分治合并 O(kn log k) O(log k)（递归栈空间）最小堆 O(kn log k) O(k)

Q35、LRU 缓存

1、题目描述

请你设计并实现一个满足 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); // 返回 1lRUCache.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); // 返回 3lRUCache.get(4); // 返回 4

提示：

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

2、解题思路

哈希表+双向链表

哈希表：用于快速查找键值对，存储键到链表节点的映射
双向链表：维护键值对的访问顺序，最近访问的放在头部，最久未用的放在尾部
操作实现 ：
- get：通过哈希表查找，存在则移动到链表头部
- put：存在则更新并移动到头部；不存在则插入到头部，容量满时删除尾部节点

3、代码实现

C++

class LRUCache {private: struct DLinkedNode { int key, value; DLinkedNode* prev; DLinkedNode* next; DLinkedNode() : key(0), value(0), prev(nullptr), next(nullptr) {} DLinkedNode(int _key, int _value) : key(_key), value(_value), prev(nullptr), next(nullptr) {} }; unordered_map cache; DLinkedNode* head; // 虚拟头节点 DLinkedNode* tail; // 虚拟尾节点 int size; int capacity;public: LRUCache(int capacity) : capacity(capacity), size(0) { // 使用虚拟头尾节点简化边界条件处理 head = new DLinkedNode(); tail = new DLinkedNode(); head->next = tail; tail->prev = head; } int get(int key) { if (!cache.count(key)) { return -1; } // 如果 key 存在, 先通过哈希表定位, 再移到头部 DLinkedNode* node = cache[key]; moveToHead(node); return node->value; } void put(int key, int value) { if (!cache.count(key)) { // 如果 key 不存在, 创建一个新的节点 DLinkedNode* node = new DLinkedNode(key, value); // 添加进哈希表 cache[key] = node; // 添加至双向链表的头部 addToHead(node); ++size; if (size > capacity) { // 如果超出容量, 删除双向链表的尾部节点 DLinkedNode* removed = removeTail(); // 删除哈希表中对应的项 cache.erase(removed->key); // 防止内存泄漏 delete removed; --size; } } else { // 如果 key 存在, 先通过哈希表定位, 再修改 value, 并移到头部 DLinkedNode* node = cache[key]; node->value = value; moveToHead(node); } }private: void addToHead(DLinkedNode* node) { node->prev = head; node->next = head->next; head->next->prev = node; head->next = node; } void removeNode(DLinkedNode* node) { node->prev->next = node->next; node->next->prev = node->prev; } void moveToHead(DLinkedNode* node) { removeNode(node); addToHead(node); } DLinkedNode* removeTail() { DLinkedNode* node = tail->prev; removeNode(node); return node; }};

Java

class LRUCache { class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; public DLinkedNode() { } public DLinkedNode(int _key, int _value) { key = _key; value = _value; } } private Map<Integer, DLinkedNode> cache = new HashMap<>(); private int size; private int capacity; private DLinkedNode head, tail; public LRUCache(int capacity) { this.size = 0; this.capacity = capacity; // 使用伪头部和伪尾部节点 head = new DLinkedNode(); tail = new DLinkedNode(); head.next = tail; tail.prev = head; } public int get(int key) { DLinkedNode node = cache.get(key); if (node == null) { return -1; } // 如果key存在，先通过哈希表定位，再移到头部 moveToHead(node); return node.value; } public void put(int key, int value) { DLinkedNode node = cache.get(key); if (node == null) { // 如果key不存在，创建一个新的节点 DLinkedNode newNode = new DLinkedNode(key, value); // 添加进哈希表 cache.put(key, newNode); // 添加至双向链表的头部 addToHead(newNode); ++size; if (size > capacity) { // 如果超出容量，删除双向链表的尾部节点 DLinkedNode tail = removeTail(); // 删除哈希表中对应的项 cache.remove(tail.key); --size; } } else { // 如果key存在，先通过哈希表定位，再修改value，并移到头部 node.value = value; moveToHead(node); } } private void addToHead(DLinkedNode node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } private void removeNode(DLinkedNode node) { node.prev.next = node.next; node.next.prev = node.prev; } private void moveToHead(DLinkedNode node) { removeNode(node); addToHead(node); } private DLinkedNode removeTail() { DLinkedNode res = tail.prev; removeNode(res); return res; }}

Python

class DLinkedNode: def __init__(self, key=0, value=0): self.key = key self.value = value self.prev = None self.next = Noneclass LRUCache: def __init__(self, capacity: int): self.cache = dict() self.capacity = capacity self.size = 0 # 使用伪头部和伪尾部节点 self.head = DLinkedNode() self.tail = DLinkedNode() self.head.next = self.tail self.tail.prev = self.head def get(self, key: int) -> int: if key not in self.cache: return -1 # 如果key存在，先通过哈希表定位，再移到头部 node = self.cache[key] self.moveToHead(node) return node.value def put(self, key: int, value: int) -> None: if key not in self.cache: # 如果key不存在，创建一个新的节点 node = DLinkedNode(key, value) # 添加进哈希表 self.cache[key] = node # 添加至双向链表的头部 self.addToHead(node) self.size += 1 if self.size > self.capacity: # 如果超出容量，删除双向链表的尾部节点 removed = self.removeTail() # 删除哈希表中对应的项 self.cache.pop(removed.key) self.size -= 1 else: # 如果key存在，先通过哈希表定位，再修改value，并移到头部 node = self.cache[key] node.value = value self.moveToHead(node) def addToHead(self, node: DLinkedNode) -> None: node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = node def removeNode(self, node: DLinkedNode) -> None: node.prev.next = node.next node.next.prev = node.prev def moveToHead(self, node: DLinkedNode) -> None: self.removeNode(node) self.addToHead(node) def removeTail(self) -> DLinkedNode: node = self.tail.prev self.removeNode(node) return node

4、复杂度分析

操作时间复杂度空间复杂度 get O(1) O(capacity) put O(1) O(capacity)

8、二叉树

Q36、二叉树的中序遍历

1、题目描述

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

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

树中节点数目在范围 [0, 100] 内

-100 <= Node.val <= 100

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

2、解题思路

方法一：递归法

递归定义：中序遍历顺序为左子树-根节点-右子树
递归终止条件：当前节点为空时返回
递归过程：先递归遍历左子树，然后访问当前节点，最后递归遍历右子树

方法二：迭代法（使用栈）

栈模拟递归：使用栈来模拟递归的调用过程
遍历过程 ：
- 先将所有左子节点入栈
- 弹出栈顶节点并访问
- 转向处理右子树

3、代码实现

C++

// 方法1: 递归法class Solution {public: vector inorderTraversal(TreeNode* root) { vector result; inorder(root, result); return result; }private: void inorder(TreeNode* node, vector& res) { if (node == nullptr) { return; } inorder(node->left, res); // 遍历左子树 res.push_back(node->val); // 访问当前节点 inorder(node->right, res); // 遍历右子树 }};

// 方法2: 迭代法class Solution {public: vector inorderTraversal(TreeNode* root) { vector result; stack st; TreeNode* curr = root; while (curr != nullptr || !st.empty()) { // 将当前节点及其所有左子节点入栈 while (curr != nullptr) { st.push(curr); curr = curr->left; } // 访问栈顶节点 curr = st.top(); st.pop(); result.push_back(curr->val); // 转向处理右子树 curr = curr->right; } return result; }};

Java

// 方法1: 递归法class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); inorder(root, res); return res; } private void inorder(TreeNode node, List<Integer> res) { if (node == null) { return; } inorder(node.left, res); // 遍历左子树 res.add(node.val); // 访问当前节点 inorder(node.right, res); // 遍历右子树 }}

// 方法2: 迭代法class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); TreeNode curr = root; while (curr != null || !stack.isEmpty()) { // 将当前节点及其所有左子节点入栈 while (curr != null) { stack.push(curr); curr = curr.left; } // 访问栈顶节点 curr = stack.pop(); res.add(curr.val); // 转向处理右子树 curr = curr.right; } return res; }}

Python

# 方法1: 递归法class Solution: def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: res = [] self.inorder(root, res) return res def inorder(self, node, res): if not node: return self.inorder(node.left, res) # 遍历左子树 res.append(node.val) # 访问当前节点 self.inorder(node.right, res) # 遍历右子树

# 方法2: 迭代法class Solution: def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: res = [] stack = [] curr = root while curr or stack: # 将当前节点及其所有左子节点入栈 while curr: stack.append(curr) curr = curr.left # 访问栈顶节点 curr = stack.pop() res.append(curr.val) # 转向处理右子树 curr = curr.right  return res

4、复杂度分析

方法时间复杂度空间复杂度递归法 O(n) O(h)（递归栈空间，h为树高度）迭代法 O(n) O(h)（栈空间）

Q37、二叉树的最大深度

1、题目描述

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

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

示例 1：
输入：root = [3,9,20,null,null,15,7]输出：3
示例 2：
输入：root = [1,null,2]输出：2
提示：

树中节点的数量在 [0, 104] 区间内。

-100 <= Node.val <= 100

2、解题思路

递归法

递归终止条件：当节点为空时深度为0
递归过程：分别计算左右子树深度
结果计算：取左右子树深度较大值加1（当前节点）

迭代法

队列初始化：将根节点放入队列
层次遍历 ：
- 记录当前层节点数
- 深度计数器加1
- 遍历当前层所有节点，并将它们的子节点加入队列
终止条件：队列为空时遍历结束

3、代码实现

C++

// 方法1: 递归法class Solution {public: int maxDepth(TreeNode* root) { if (root == nullptr) { return 0; } int leftDepth = maxDepth(root->left); // 计算左子树深度 int rightDepth = maxDepth(root->right); // 计算右子树深度 // 返回较大深度加 1 (当前节点) return max(leftDepth, rightDepth) + 1; }};

// 方法2: 迭代法class Solution {public: int maxDepth(TreeNode* root) { if (root == nullptr) { return 0; } queue q; q.push(root); int depth = 0; while (!q.empty()) { int levelSize = q.size(); // 当前层节点数 depth++;  // 深度+1 // 遍历当前层所有节点 for (int i = 0; i left) {  q.push(node->left); } if (node->right) {  q.push(node->right); } } } return depth; }};

Java

// 方法1: 递归法class Solution { public int maxDepth(TreeNode root) { if (root == null) { return 0; } int leftDepth = maxDepth(root.left); // 计算左子树深度 int rightDepth = maxDepth(root.right); // 计算右子树深度 // 返回较大深度加1（当前节点） return Math.max(leftDepth, rightDepth) + 1; }}

// 方法2: 迭代法class Solution { public int maxDepth(TreeNode root) { if (root == null) { return 0; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int depth = 0; while (!queue.isEmpty()) { int levelSize = queue.size(); // 当前层节点数 depth++; // 深度加1 // 遍历当前层所有节点 for (int i = 0; i < levelSize; i++) { TreeNode node = queue.poll(); // 将下一层节点加入队列 if (node.left != null) {  queue.offer(node.left); } if (node.right != null) {  queue.offer(node.right); } } } return depth; }}

Python

# 方法1: 递归法class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: if not root: return 0 left_depth = self.maxDepth(root.left) # 计算左子树深度 right_depth = self.maxDepth(root.right) # 计算右子树深度 # 返回较大深度加1（当前节点） return max(left_depth, right_depth) + 1

# 方法2: 迭代法class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: if not root: return 0 queue = deque([root]) depth = 0 while queue: level_size = len(queue) # 当前层节点数 depth += 1  # 深度加1 # 遍历当前层所有节点 for _ in range(level_size): node = queue.popleft() # 将下一层节点加入队列 if node.left:  queue.append(node.left) if node.right:  queue.append(node.right) return depth

4、复杂度分析

方法时间复杂度空间复杂度递归法 O(n) O(h)（递归栈空间，h为树高度）迭代法 O(n) O(n)（最坏情况队列存储）

Q38、翻转二叉树

1、题目描述

给你一棵二叉树的根节点 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

2、解题思路

方法一：递归法

递归终止条件：当前节点为空时返回
交换操作：交换当前节点的左右子树
递归过程：递归地对左右子树进行翻转

方法二：迭代法（使用队列）

层次遍历：使用队列进行广度优先遍历
交换操作：对每个出队节点交换其左右子树
子节点入队：将交换后的左右子节点（如果存在）加入队列

3、代码实现

C++

// 方法1: 递归法class Solution {public: TreeNode* invertTree(TreeNode* root) { if (root == nullptr) { return nullptr; } // 交换左右子树 TreeNode* tmp = root->left; root->left = root->right; root->right = tmp; // 递归翻转左右子树 invertTree(root->left); invertTree(root->right); return root; }};

// 方法2: 迭代法class Solution {public: TreeNode* invertTree(TreeNode* root) { if (root == nullptr) { return nullptr; } queue q; q.push(root); while (!q.empty()) { TreeNode* current = q.front(); q.pop(); // 交换左右子树 TreeNode* tmp = current->left; current->left = current->right; current->right = tmp; // 将子节点加入队列 if (current->left) { q.push(current->left); } if (current->right) { q.push(current->right); } } return root; }};

Java

// 方法1: 递归法class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } // 交换左右子树 TreeNode temp = root.left; root.left = root.right; root.right = temp; // 递归翻转左右子树 invertTree(root.left); invertTree(root.right); return root; }}

// 方法2: 迭代法class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode current = queue.poll(); // 交换左右子树 TreeNode temp = current.left; current.left = current.right; current.right = temp; // 将子节点加入队列 if (current.left != null) { queue.offer(current.left); } if (current.right != null) { queue.offer(current.right); } } return root; }}

Python

# 方法1: 递归法class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if not root: return None # 交换左右子树 root.left, root.right = root.right, root.left # 递归翻转左右子树 self.invertTree(root.left) self.invertTree(root.right) return root

# 方法2: 迭代法class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if not root: return None queue = deque([root]) while queue: current = queue.popleft() # 交换左右子树 current.left, current.right = current.right, current.left # 将子节点加入队列 if current.left: queue.append(current.left) if current.right: queue.append(current.right) return root

4、复杂度分析

方法时间复杂度空间复杂度递归法 O(n) O(h)（递归栈空间，h为树高度）迭代法 O(n) O(n)（最坏情况队列存储）

Q39、对称二叉树

1、题目描述

给你一个二叉树的根节点 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

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

2、解题思路

方法一：递归法

对称条件

：一棵树是对称的当且仅当：
- 它的左右子树互为镜像
- 左子树的左子树与右子树的右子树互为镜像
- 左子树的右子树与右子树的左子树互为镜像
递归终止条件 ：
- 两个节点都为空：返回true
- 一个为空一个不为空：返回false
- 节点值不相等：返回false
递归过程：比较左子树的左子树与右子树的右子树，以及左子树的右子树与右子树的左子树

方法二：迭代法（使用队列）

队列初始化：将根节点的左右子节点成对加入队列
队列处理 ：
- 每次取出两个节点进行比较
- 如果都为空则继续
- 如果一个为空一个不为空或值不相等则返回false
- 将左节点的左子节点与右节点的右子节点，以及左节点的右子节点与右节点的左子节点成对加入队列
终止条件：队列为空时返回true

3、代码实现

C++

// 方法1: 递归法class Solution {public: bool isSymmetric(TreeNode* root) { if (root == nullptr) { return true; } return compare(root->left, root->right); }private: bool compare(TreeNode* left, TreeNode* right) { // 两个节点都为空 if (left == nullptr && right == nullptr) { return true; } // 一个为空一个不为空 if (left == nullptr || right == nullptr) { return false; } // 结点的值不相等 if (left->val != right->val) { return false; } // 递归比较左子树的左子树与右子树的右子树, // 以及左子树的右子树与右子树的左子树 return compare(left->left, right->right) && compare(left->right, right->left); }};

// 方法2: 迭代法class Solution {public: bool isSymmetric(TreeNode* root) { if (root == nullptr) { return true; } queue q; q.push(root->left); q.push(root->right); while (!q.empty()) { TreeNode* left = q.front(); q.pop(); TreeNode* right = q.front(); q.pop(); // 两个节点都为空 if (left == nullptr && right == nullptr) { continue; } // 一个为空一个不为空 if (left == nullptr || right == nullptr) { return false; } // 节点不相等 if (left->val != right->val) { return false; } // 将需要比较的节点成对加入队列 q.push(left->left); q.push(right->right); q.push(left->right); q.push(right->left); } return true; }};

Java

// 方法1: 递归法class Solution { public boolean isSymmetric(TreeNode root) { if (root == null) { return true; } return compare(root.left, root.right); } private boolean compare(TreeNode left, TreeNode right) { // 两个节点都为空 if (left == null && right == null) { return true; } // 一个为空一个不为空 if (left == null || right == null) { return false; } // 节点值不相等 if (left.val != right.val) { return false; } // 递归比较左子树的左子树与右子树的右子树，以及左子树的右子树与右子树的左子树 return compare(left.left, right.right) && compare(left.right, right.left); }}

// 方法2: 迭代法class Solution { public boolean isSymmetric(TreeNode root) { if (root == null) { return true; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root.left); queue.offer(root.right); while (!queue.isEmpty()) { TreeNode left = queue.poll(); TreeNode right = queue.poll(); // 两个节点都为空 if (left == null && right == null) { continue; } // 一个为空一个不为空 if (left == null || right == null) { return false; } // 节点值不相等 if (left.val != right.val) { return false; } // 将需要比较的节点成对加入队列 queue.offer(left.left); queue.offer(right.right); queue.offer(left.right); queue.offer(right.left); } return true; }}

Python

# 方法1: 递归法class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: if not root: return True return self.compare(root.left, root.right) def compare(self, left: Optional[TreeNode], right: Optional[TreeNode]) -> bool: # 两个节点都为空 if not left and not right: return True # 一个为空一个不为空 if not left or not right: return False # 节点值不相等 if left.val != right.val: return False # 递归比较左子树的左子树与右子树的右子树，以及左子树的右子树与右子树的左子树 return self.compare(left.left, right.right) and self.compare(left.right, right.left)

# 方法2: 迭代法class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: if not root: return True queue = deque() queue.append(root.left) queue.append(root.right) while queue: left = queue.popleft() right = queue.popleft() # 两个节点都为空 if not left and not right: continue # 一个为空一个不为空 if not left or not right: return False # 节点值不相等 if left.val != right.val: return False # 将需要比较的节点成对加入队列 queue.append(left.left) queue.append(right.right) queue.append(left.right) queue.append(right.left) return True

4、复杂度分析

方法时间复杂度空间复杂度递归法 O(n) O(h)（递归栈空间，h为树高度）迭代法 O(n) O(n)（最坏情况队列存储）

Q40、二叉树的直径

1、题目描述

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

二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 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

2、解题思路

方法：深度优先搜索（DFS）

直径定义：任意两个节点间最长路径的边数
关键观察 ：
- 树的最长路径不一定经过根节点
- 最长路径可能存在于某个节点的左右子树中最长路径的组合
递归过程 ：
- 计算每个节点的左右子树的深度
- 更新当前最大直径（左深度+右深度）
- 返回当前节点的深度（较大子树深度+1）

3、代码实现

C++

class Solution {private: int max_diameter = 0; // 记录最大直径 int depth(TreeNode* root) { if (root == nullptr) { return 0; } // 计算左右子树的深度 int left_depth = depth(root->left); int right_depth = depth(root->right); // 更新最大直径 (节点数减 1 等于边数) max_diameter = max(max_diameter, left_depth + right_depth); // 返回当前节点的深度 (较大子树深度 +1) return max(left_depth, right_depth) + 1; }public: int diameterOfBinaryTree(TreeNode* root) { depth(root); return max_diameter; }};

Java

class Solution { private int maxDiameter = 0; public int diameterOfBinaryTree(TreeNode root) { depth(root); return maxDiameter; } private int depth(TreeNode root) { if (root == null) { return 0; } int leftDepth = depth(root.left); int rightDepth = depth(root.right); // 更新最大直径 maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth); // 返回当前节点的深度 return Math.max(leftDepth, rightDepth) + 1; }}

Python

class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: self.max_diameter = 0 def depth(node): if not node: return 0 left_depth = depth(node.left) right_depth = depth(node.right) # 更新最大直径 self.max_diameter = max(self.max_diameter, left_depth + right_depth) # 返回当前节点的深度 return max(left_depth, right_depth) + 1 depth(root) return self.max_diameter

4、复杂度分析

时间复杂度：O(n)，每个节点只访问一次
空间复杂度：O(h)，递归栈空间，h为树的高度

Q41、二叉树的层序遍历

1、题目描述

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

示例 1：
输入：root = [3,9,20,null,null,15,7]输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]输出：[[1]]
示例 3：
输入：root = []输出：[]
提示：

树中节点数目在范围 [0, 2000] 内

-1000 <= Node.val <= 1000

2、解题思路

方法：广度优先搜索（BFS）使用队列

初始化：创建结果容器和队列，将根节点入队
循环处理 ：
- 记录当前层的节点数量
- 创建当前层的值容器
- 处理当前层所有节点：
  - 出队节点并记录值
  - 将左右子节点（如果存在）入队
保存结果：将当前层的值容器加入结果
终止条件：队列为空时结束

3、代码实现

C++

class Solution {public: vector<vector> levelOrder(TreeNode* root) { vector<vector> result; // 存储最终结果 if (root == nullptr) { return result; } queue q; // 辅助列表 q.push(root); while (!q.empty()) { int level_size = q.size(); // 当前层的节点数 vector current_level; // 存储当前层的节点值 // 处理当前层所有节点 for (int i = 0; i val); // 将子节点加入队列 if (node->left) {  q.push(node->left); } if (node->right) {  q.push(node->right); } } result.push_back(current_level); // 将当前层加入结果 } return result; }};

Java

class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) { return result; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); List<Integer> currentLevel = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { TreeNode node = queue.poll(); currentLevel.add(node.val); if (node.left != null) {  queue.offer(node.left); } if (node.right != null) {  queue.offer(node.right); } } result.add(currentLevel); } return result; }}

Python

class Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: result = [] if not root: return result queue = deque([root]) while queue: level_size = len(queue) current_level = [] for _ in range(level_size): node = queue.popleft() current_level.append(node.val) if node.left:  queue.append(node.left) if node.right:  queue.append(node.right) result.append(current_level) return result

4、复杂度分析

时间复杂度：O(n)，每个节点访问一次
空间复杂度：O(n)，最坏情况下队列存储所有叶子节点

Q42、将有序数组转换为二叉搜索树

1、题目描述

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树。

示例 1：
输入：nums = [-10,-3,0,5,9]输出：[0,-3,9,-10,null,5]解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
示例 2：
输入：nums = [1,3]输出：[3,1]解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
提示：

1 <= nums.length <= 104

-104 <= nums[i] <= 104

nums 按 严格递增 顺序排列

2、解题思路

方法：递归分治法

平衡BST性质 ：
- 左子树所有节点值 < 根节点值
- 右子树所有节点值 > 根节点值
- 左右子树高度差不超过1
关键观察 ：
- 有序数组的中间元素适合作为根节点
- 左右子数组可以递归构建左右子树
实现步骤 ：
- 找到数组中间元素作为根节点
- 左子数组构建左子树
- 右子数组构建右子树

3、代码实现

C++

// 方法1: 选择中间左边的元素作为根class Solution {public: TreeNode* sortedArrayToBST(vector& nums) { return buildBST(nums, 0, nums.size() - 1); }private: TreeNode* buildBST(vector& nums, int left, int right) { if (left > right) { return nullptr; } // 选择中间左边元素作为根 int mid = left + (right - left) / 2; TreeNode* root = new TreeNode(nums[mid]); root->left = buildBST(nums, left, mid - 1); root->right = buildBST(nums, mid + 1, right); return root; }};

// 方法2: 选择中间右边的元素作为根class Solution {public: TreeNode* sortedArrayToBST(vector& nums) { return buildBST(nums, 0, nums.size() - 1); }private: TreeNode* buildBST(vector& nums, int left, int right) { if (left > right) { return nullptr; } // 选择中间左边元素作为根 int mid = left + (right - left + 1) / 2; TreeNode* root = new TreeNode(nums[mid]); root->left = buildBST(nums, left, mid - 1); root->right = buildBST(nums, mid + 1, right); return root; }};

Java

class Solution { public TreeNode sortedArrayToBST(int[] nums) { return buildBST(nums, 0, nums.length - 1); } private TreeNode buildBST(int[] nums, int left, int right) { if (left > right) { return null; } int mid = left + (right - left) / 2; TreeNode root = new TreeNode(nums[mid]); root.left = buildBST(nums, left, mid - 1); root.right = buildBST(nums, mid + 1, right); return root; }}

Python

class Solution: def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]: def build_bst(left, right): if left > right: return None mid = (left + right) // 2 # 偏左选择 root = TreeNode(nums[mid]) root.left = build_bst(left, mid - 1) root.right = build_bst(mid + 1, right) return root return build_bst(0, len(nums) - 1)

4、复杂度分析

时间复杂度：O(n)，每个元素访问一次
空间复杂度：O(logn)，递归栈空间

Q43、验证二叉搜索树

1、题目描述

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：
输入：root = [2,1,3]输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6]输出：false解释：根节点的值是 5 ，但是右子节点的值是 4 。
提示：

树中节点数目范围在[1, 104] 内

-231 <= Node.val <= 231 - 1

2、解题思路

方法一：递归中序遍历

BST性质：中序遍历 BST 得到的是升序序列
递归过程 ：
- 递归检查左子树
- 检查当前节点是否大于前驱节点
- 更新前驱节点为当前节点值
- 递归检查右子树
边界处理：使用 LONG_MIN 作为初始前驱值

方法二：迭代中序遍历

使用栈实现中序遍历
迭代过程 ：
- 将所有左子节点压栈
- 弹出节点并检查是否大于前驱
- 更新前驱并转向右子树
终止条件：栈空且当前节点为空

3、代码实现

C++

// 方法1: 递归中序遍历class Solution {private: long prev = LONG_MIN; // 记录前驱节点值public: bool isValidBST(TreeNode* root) { if (!root) { return true; } // 检查左子树 if (!isValidBST(root->left)) { return false; } // 检查当前节点 if (root->val val; // 更新前驱 // 检查右子树 return isValidBST(root->right); }};

// 方法2: 迭代中序遍历class Solution {public: bool isValidBST(TreeNode* root) { stack st; long prev = LONG_MIN; while (!st.empty() || root) { // 将所有左子节点压栈 while (root) { st.push(root); root = root->left; } root = st.top(); st.pop(); // 检查当前节点 if (root->val val; // 转向右子树 root = root->right; } return true; }};

Java

// 方法1: 递归中序遍历class Solution { private long prev = Long.MIN_VALUE; public boolean isValidBST(TreeNode root) { if (root == null) { return true; } if (!isValidBST(root.left)) { return false; } if (root.val <= prev) { return false; } prev = root.val; return isValidBST(root.right); }}

// 方法2: 迭代中序遍历class Solution { public boolean isValidBST(TreeNode root) { Deque<TreeNode> stack = new ArrayDeque<>(); long prev = Long.MIN_VALUE; while (!stack.isEmpty() || root != null) { while (root != null) { stack.push(root); root = root.left; } root = stack.pop(); if (root.val <= prev) { return false; } prev = root.val; root = root.right; } return true; }}

Python

# 方法1: 递归中序遍历class Solution: def isValidBST(self, root: Optional[TreeNode]) -> bool: self.prev = float(\'-inf\') def helper(node): if not node: return True if not helper(node.left): return False if node.val <= self.prev: return False self.prev = node.val return helper(node.right) return helper(root)

# 方法2: 迭代中序遍历class Solution: def isValidBST(self, root: Optional[TreeNode]) -> bool: stack = [] prev = float(\'-inf\') while stack or root: while root: stack.append(root) root = root.left root = stack.pop() if root.val <= prev: return False prev = root.val root = root.right return True

4、复杂度分析

时间复杂度：O(n)，每个节点访问一次
空间复杂度：O(n)，最坏情况下递归栈或显式栈空间

Q44、二叉搜索树中第 K 小的元素

1、题目描述

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

示例 1：
输入：root = [3,1,4,null,2], k = 1输出：1
示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3输出：3
提示：

树中的节点数为 n 。

1 <= k <= n <= 104

0 <= Node.val <= 104

**进阶：**如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

2、解题思路

方法一：递归中序遍历

BST性质：中序遍历BST得到的是升序序列
递归过程 ：
- 递归遍历左子树
- 处理当前节点（k减1，检查是否找到第k小的元素）
- 递归遍历右子树
终止条件：找到第k小的元素或遍历完成

方法二：迭代中序遍历

使用栈实现中序遍历
迭代过程 ：
- 将所有左子节点压栈
- 弹出节点并检查是否为第k小的元素
- 转向右子树
优化：找到目标后立即终止遍历

3、代码实现

C++

// 方法1: 递归中序遍历class Solution {public: int kthSmallest(TreeNode* root, int k) { int result = 0; inorder(root, k, result); return result; }private: void inorder(TreeNode* root, int& k, int& result) { if (!root || k == 0) { return; } inorder(root->left, k, result); // 遍历左子树 if (--k == 0) { result = root->val; return; } inorder(root->right, k, result); // 遍历右子树 }};

// 方法2: 迭代中序遍历class Solution {public: int kthSmallest(TreeNode* root, int k) { stack s; while (true) { // 将所有左子节点压栈 while (root) { s.push(root); root = root->left; } root = s.top(); s.pop(); if (--k == 0) // 找到第 k 小的元素 { return root->val; } root = root->right; // 转向右子树 } }};

Java

// 方法1: 递归中序遍历class Solution { private int result; private int count; public int kthSmallest(TreeNode root, int k) { count = k; inorder(root); return result; } private void inorder(TreeNode node) { if (node == null || count == 0) { return; } inorder(node.left); // 遍历左子树 if (--count == 0) { // 处理当前节点 result = node.val; return; } inorder(node.right); // 遍历右子树 }}

// 方法2: 迭代中序遍历class Solution { public int kthSmallest(TreeNode root, int k) { Deque<TreeNode> stack = new ArrayDeque<>(); while (true) { // 将所有左子节点压栈 while (root != null) { stack.push(root); root = root.left; } root = stack.pop(); if (--k == 0) { // 找到第k小的元素 return root.val; } root = root.right; // 转向右子树 } }}

Python

# 方法1: 递归中序遍历class Solution: def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: self.k = k self.result = 0 self.inorder(root) return self.result def inorder(self, node): if not node or self.k == 0: return self.inorder(node.left) # 遍历左子树 self.k -= 1 if self.k == 0: # 处理当前节点 self.result = node.val return self.inorder(node.right) # 遍历右子树

# 方法2: 迭代中序遍历class Solution: def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: stack = [] while True: # 将所有左子节点压栈 while root: stack.append(root) root = root.left root = stack.pop() k -= 1 if k == 0: # 找到第k小的元素 return root.val root = root.right # 转向右子树

4、复杂度分析

时间复杂度：O(H+k)，其中H是树的高度，最坏情况下O(n)
空间复杂度：
- 递归：O(H)，递归栈空间
- 迭代：O(H)，显式栈空间

Q45、二叉树的右视图

1、题目描述

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1：

**输入：**root = [1,2,3,null,5,null,4]

输出：[1,3,4]

解释：

示例 2：

**输入：**root = [1,2,3,4,null,null,null,5]

输出：[1,3,4,5]

解释：

示例 3：

**输入：**root = [1,null,3]

输出：[1,3]

示例 4：

**输入：**root = []

输出：[]

提示:

二叉树的节点个数的范围是 [0,100]

-100 <= Node.val <= 100

2、解题思路

方法一：广度优先搜索（BFS）

层次遍历：使用队列进行层序遍历
记录每层最后一个节点：每层遍历结束时，队列中最后一个节点即为该层最右可见节点
时间复杂度：O(n)，每个节点访问一次
空间复杂度：O(n)，队列空间

方法二：深度优先搜索（DFS）

递归遍历：优先访问右子树
记录每层第一个访问的节点：每层第一次访问的节点即为该层最右可见节点
时间复杂度：O(n)，每个节点访问一次
空间复杂度：O(h)，递归栈空间（h为树高）

方法三：迭代DFS

使用显式栈：模拟递归过程
记录每层第一个访问的节点：类似递归DFS
时间复杂度：O(n)
空间复杂度：O(h)

3、代码实现

C++

// 方法1: BFS (层序遍历)class Solution {public: vector rightSideView(TreeNode* root) { vector result; if (!root) { return result; } queue q; q.push(root); while (!q.empty()) { int size = q.size(); for (int i = 0; i val); } if (node->left) {  q.push(node->left); } if (node->right) {  q.push(node->right); } } } return result; }};

// 方法2: DFS (递归)class Solution {public: vector rightSideView(TreeNode* root) { vector result; dfs(root, 0, result); return result; }private: void dfs(TreeNode* node, int depth, vector& result) { if (!node) { return; } // 每层第一次访问的节点即为最右可见节点 if (depth == result.size()) { result.push_back(node->val); } // 优先访问右子树 dfs(node->right, depth + 1, result); dfs(node->left, depth + 1, result); }};

// 方法3: DFS (迭代)class Solution {public: vector rightSideView(TreeNode* root) { vector result; if (!root) { return result; } stack<pair> s; s.push({root, 0}); while (!s.empty()) { auto [node, depth] = s.top(); s.pop(); if (depth == result.size()) { result.push_back(node->val); } // 注意压栈顺序, 先左后右才能保证先访问右子树 if (node->left) { s.push({node->left, depth + 1}); } if (node->right) { s.push({node->right, depth + 1}); } } return result; }};

Java

// 方法1: BFSclass Solution { public List<Integer> rightSideView(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) { return result; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); if (i == size - 1) {  result.add(node.val); } if (node.left != null)  queue.offer(node.left); if (node.right != null)  queue.offer(node.right); } } return result; }}

// 方法2: DFSclass Solution { public List<Integer> rightSideView(TreeNode root) { List<Integer> result = new ArrayList<>(); dfs(root, 0, result); return result; } private void dfs(TreeNode node, int depth, List<Integer> result) { if (node == null) { return; } if (depth == result.size()) { result.add(node.val); } dfs(node.right, depth + 1, result); dfs(node.left, depth + 1, result); }}

Python

# BFSclass Solution: def rightSideView(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] result = [] queue = collections.deque([root]) while queue: size = len(queue) for i in range(size): node = queue.popleft() if i == size - 1:  result.append(node.val) if node.left:  queue.append(node.left) if node.right:  queue.append(node.right) return result

# DFSclass Solution: def rightSideView(self, root: Optional[TreeNode]) -> List[int]: result = [] def dfs(node, depth): if not node: return if depth == len(result): result.append(node.val) dfs(node.right, depth + 1) dfs(node.left, depth + 1) dfs(root, 0) return result

4、复杂度分析

方法时间复杂度空间复杂度特点 BFS O(n) O(n) 直观，适用于层相关操作递归DFS O(n) O(h) 代码简洁，可能栈溢出迭代DFS O(n) O(h) 避免递归栈溢出

选择建议：

通常推荐BFS方法，直观易理解
对于非常深的树，考虑迭代DFS避免栈溢出
递归DFS适合树高不大的情况

Q46、二叉树展开为链表

1、题目描述

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：
输入：root = [1,2,5,3,4,null,6]输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
输入：root = []输出：[]
示例 3：
输入：root = [0]输出：[0]
提示：

树中结点数在范围 [0, 2000] 内

-100 <= Node.val <= 100

**进阶：**你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

2、解题思路

方法一：递归先序遍历+存储节点

先序遍历：递归地收集所有节点到列表中
重构链表：遍历列表，将每个节点的左指针置空，右指针指向下一个节点
复杂度 ：
- 时间复杂度：O(n)
- 空间复杂度：O(n)，需要存储所有节点

方法二：迭代先序遍历

使用栈：显式地模拟先序遍历过程
边遍历边构建：维护一个 prev 指针，每次处理当前节点时更新前驱节点的指针
复杂度 ：
- 时间复杂度：O(n)
- 空间复杂度：O(n)，栈空间

方法三：原地修改（O(1)空间）

寻找前驱节点：对于每个节点，找到其左子树的最右节点作为前驱
修改指针：将当前节点的右子树接到前驱节点的右指针上
移动指针：将左子树移到右子树位置，左指针置空
复杂度 ：
- 时间复杂度：O(n)
- 空间复杂度：O(1)

方法四：后序遍历变形

逆向后序遍历：按照右-左-根的顺序访问节点
维护全局指针：在访问每个节点时，将其右指针指向前一个访问的节点
复杂度 ：
- 时间复杂度：O(n)
- 空间复杂度：O(h)，递归栈空间（h为树高）

3、代码实现

C++

// 方法1: 递归先序遍历 + 存储节点class Solution {public: void flatten(TreeNode* root) { vector nodes; preorder(root, nodes); for (int i = 1; i left = nullptr; nodes[i - 1]->right = nodes[i]; } }private: void preorder(TreeNode* node, vector& nodes) { if (!node) { return; } nodes.push_back(node); preorder(node->left, nodes); preorder(node->right, nodes); }};

// 方法2: 迭代先序遍历class Solution {public: void flatten(TreeNode* root) { if (!root) { return; } stack s; s.push(root); TreeNode* prev = nullptr; while (!s.empty()) { TreeNode* cur = s.top(); s.pop(); if (prev) { prev->left = nullptr; prev->right = cur; } if (cur->right) { s.push(cur->right); } if (cur->left) { s.push(cur->left); } prev = cur; } }};

// 方法3: 原地修改 (O(1)空间)class Solution {public: void flatten(TreeNode* root) { TreeNode* cur = root; while (cur) { if (cur->left) { TreeNode* next = cur->left; TreeNode* predecessor = next; while (predecessor->right) {  predecessor = predecessor->right; } predecessor->right = cur->right; cur->right = next; cur->left = nullptr; } cur = cur->right; } }};

// 方法4: 后序遍历变形class Solution {private: TreeNode* prev = nullptr;public: void flatten(TreeNode* root) { if (!root) { return; } flatten(root->right); flatten(root->left); root->right = prev; root->left = nullptr; prev = root; }};

Java

// 方法3: 原地修改class Solution { public void flatten(TreeNode root) { TreeNode curr = root; while (curr != null) { if (curr.left != null) { TreeNode next = curr.left; TreeNode predecessor = next; while (predecessor.right != null) {  predecessor = predecessor.right; } predecessor.right = curr.right; curr.right = next; curr.left = null; } curr = curr.right; } }}

Python

# 方法3: 原地修改class Solution: def flatten(self, root: Optional[TreeNode]) -> None: \"\"\" Do not return anything, modify root in-place instead. \"\"\" curr = root while curr: if curr.left: predecessor = curr.left while predecessor.right:  predecessor = predecessor.right predecessor.right = curr.right curr.right = curr.left curr.left = None curr = curr.right

4、复杂度分析

方法时间复杂度空间复杂度特点递归+存储 O(n) O(n) 简单直观，但需要额外空间迭代 O(n) O(n) 避免递归，但仍需栈空间原地修改 O(n) O(1) 最优解，满足进阶要求后序变形 O(n) O(h) 递归栈空间，思路独特

Q47、从前序与中序遍历序列构造二叉树

1、题目描述

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]输出: [-1]
提示:

1 <= preorder.length <= 3000

inorder.length == preorder.length

-3000 <= preorder[i], inorder[i] <= 3000

preorder 和 inorder 均 无重复 元素

inorder 均出现在 preorder

preorder 保证为二叉树的前序遍历序列

inorder 保证为二叉树的中序遍历序列

2、解题思路

方法一：递归分治（优化版）

核心思想 ：
- 前序遍历的第一个元素是根节点
- 在中序遍历中找到根节点位置，左边是左子树，右边是右子树
- 递归构建左右子树
优化：
- 使用索引范围而非复制数组
- 使用哈希表快速定位中序索引
复杂度 ：
- 时间复杂度：O(n)
- 空间复杂度：O(n)（哈希表空间）

方法二：递归分治（基础版）

核心思想 ：
- 前序遍历的第一个元素是根节点
- 在中序遍历中找到根节点位置
- 分割数组并递归构建子树
缺点：
- 每次递归都创建新数组，空间效率低
复杂度：
- 时间复杂度：O(n²)
- 空间复杂度：O(n²)

方法三：迭代法

核心思想 ：
- 使用栈模拟递归过程
- 前序遍历顺序构建节点
- 根据中序遍历顺序确定何时回溯
优点：
- 避免递归栈溢出
复杂度 ：
- 时间复杂度：O(n)
- 空间复杂度：O(n)

3、代码实现

C++

// 方法1: 递归分治 (优化版)class Solution {public: TreeNode* buildTree(vector& preorder, vector& inorder) { // 构建中序遍历值到索引的哈希映射 for (int i = 0; i < inorder.size(); ++i) { indexMap[inorder[i]] = i; } return build(preorder, 0, preorder.size() - 1, 0, inorder.size() - 1); }private: unordered_map indexMap; TreeNode* build(vector& preorder, int preStart, int preEnd, int inStart, int inEnd) { if (preStart > preEnd) { return nullptr; } // 前序遍历的第一个节点是根节点 TreeNode* root = new TreeNode(preorder[preStart]); // 在中序遍历中找到根节点的位置 int inRoot = indexMap[root->val]; int leftSize = inRoot - inStart; // 左子树的大小 // 递归构建左子树 root->left = build(preorder, preStart + 1, preStart + leftSize, inStart, inRoot - 1); // 递归构建右子树 root->right = build(preorder, preStart + leftSize + 1, preEnd, inRoot + 1, inEnd); return root; }};

// 方法2: 递归分治 (基础版)class Solution {public: TreeNode* buildTree(vector& preorder, vector& inorder) { if (preorder.empty() || inorder.empty()) { return nullptr; } TreeNode* root = new TreeNode(preorder[0]); // 在中序遍历中找到根节点位置 auto it = find(inorder.begin(), inorder.end(), preorder[0]); int pos = it - inorder.begin(); // 构建左子树的前序和中序数组 vector leftPre(preorder.begin() + 1, preorder.begin() + 1 + pos); vector leftIn(inorder.begin(), inorder.begin() + pos); // 构建右子树的前序和中序数组 vector rightPre(preorder.begin() + 1 + pos, preorder.end()); vector rightIn(inorder.begin() + pos + 1, inorder.end()); // 递归构建左右子树 root->left = buildTree(leftPre, leftIn); root->right = buildTree(rightPre, rightIn); return root; }};

// 方法3: 迭代法class Solution {public: TreeNode* buildTree(vector& preorder, vector& inorder) { if (preorder.empty()) { return nullptr; } stack s; TreeNode* root = new TreeNode(preorder[0]); s.push(root); int inorderIndex = 0; for (int i = 1; i val != inorder[inorderIndex]) { // 当前节点不是中序的下一个节点, 说明还有右子树 node->left = new TreeNode(preorder[i]); s.push(node->left); } else { // 找到最远的右节点 while (!s.empty() && s.top()->val == inorder[inorderIndex]) {  node = s.top();  s.pop();  ++inorderIndex; } // 添加右节点 node->right = new TreeNode(preorder[i]); s.push(node->right); } } return root; }};

Java

// 方法1: 递归分治 (优化版)class Solution { private Map<Integer, Integer> indexMap; public TreeNode buildTree(int[] preorder, int[] inorder) { indexMap = new HashMap<>(); for (int i = 0; i < inorder.length; i++) { indexMap.put(inorder[i], i); } return build(preorder, 0, preorder.length - 1, 0, inorder.length - 1); } private TreeNode build(int[] preorder, int preStart, int preEnd, int inStart, int inEnd) { if (preStart > preEnd) { return null; } TreeNode root = new TreeNode(preorder[preStart]); int inRoot = indexMap.get(root.val); int leftSize = inRoot - inStart; root.left = build(preorder, preStart + 1, preStart + leftSize, inStart, inRoot - 1); root.right = build(preorder, preStart + leftSize + 1, preEnd, inRoot + 1, inEnd); return root; }}

Python

# 方法1: 递归分治 (优化版)class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: # 构建中序值到索引的映射 index_map = {val: idx for idx, val in enumerate(inorder)} def build(pre_start, pre_end, in_start, in_end): if pre_start > pre_end: return None root_val = preorder[pre_start] root = TreeNode(root_val) in_root = index_map[root_val] left_size = in_root - in_start root.left = build(pre_start+1, pre_start+left_size, in_start, in_root-1) root.right = build(pre_start+left_size+1, pre_end, in_root+1, in_end) return root return build(0, len(preorder)-1, 0, len(inorder)-1)

4、复杂度分析

方法时间复杂度空间复杂度特点递归分治（优化） O(n) O(n) 最优解，使用哈希表加速查找递归分治（基础） O(n²) O(n²) 简单但效率低，每次递归创建新数组迭代法 O(n) O(n) 避免递归，使用栈模拟调用过程

Q48、路径总和 III

1、题目描述

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8输出：3解释：和等于 8 的路径有 3 条，如图所示。
示例 2：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22输出：3
提示:

二叉树的节点个数的范围是 [0,1000]

-109 <= Node.val <= 109

-1000 <= targetSum <= 1000

2、解题思路

方法一：双重递归

外层递归：遍历每个节点，作为路径的起点
内层递归：从当前节点出发，计算所有向下路径的和
复杂度 ：
- 时间复杂度：O(n²)，最坏情况下每个节点都需要遍历其所有子节点
- 空间复杂度：O(h)，递归栈空间（h为树高）

方法二：前缀和+哈希表

前缀和思想：记录从根到当前节点的路径和
哈希表存储：保存前缀和出现的次数
查找差值：当前前缀和 - targetSum 若存在于哈希表中，说明存在满足条件的路径
复杂度 ：
- 时间复杂度：O(n)，只需遍历一次树
- 空间复杂度：O(n)，哈希表空间

3、代码实现

C++

// 方法1: 双重递归class Solution {public: int pathSum(TreeNode* root, int targetSum) { if (!root) { return 0; } // 计算以当前节点为起点的路径数 + 递归计算左右子树 return rootSum(root, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum); }private: // 计算以 root 为起点, 和为 targetSum 的路径数 int rootSum(TreeNode* root, long long targetSum) { if (!root) { return 0; } int count = 0; if (root->val == targetSum) { count++; } // 递归计算左右子树, 更新剩余和 count += rootSum(root->left, targetSum - root->val); count += rootSum(root->right, targetSum - root->val); return count; }};

// 方法2: 前缀和 + 哈希表class Solution {public: int pathSum(TreeNode* root, int targetSum) { unordered_map prefix; // 存储前缀和及其出现次数 prefix[0] = 1;  // 初始化: 前缀和为 0 出现 1 次 return dfs(root, 0, targetSum, prefix); }private: int dfs(TreeNode* root, long currSum, int target, unordered_map& prefix) { if (!root) { return 0; } currSum += root->val;  // 当前路径和 int res = prefix[currSum - target]; // 查找满足条件的路径数 prefix[currSum]++; // 更新当前前缀和计数 res += dfs(root->left, currSum, target, prefix); // 递归左子树 res += dfs(root->right, currSum, target, prefix); // 递归右子树 prefix[currSum]--; // 回溯, 恢复状态 return res; }};

Java

// 方法2: 前缀和 + 哈希表class Solution { public int pathSum(TreeNode root, int targetSum) { Map<Long, Integer> prefix = new HashMap<>(); prefix.put(0L, 1); // 初始化前缀和为0出现1次 return dfs(root, 0L, targetSum, prefix); } private int dfs(TreeNode node, long currSum, int target, Map<Long, Integer> prefix) { if (node == null) { return 0; } currSum += node.val; int res = prefix.getOrDefault(currSum - target, 0); prefix.put(currSum, prefix.getOrDefault(currSum, 0) + 1); res += dfs(node.left, currSum, target, prefix); res += dfs(node.right, currSum, target, prefix); prefix.put(currSum, prefix.get(currSum) - 1); // 回溯 return res; }}

Python

# 方法2: 前缀和 + 哈希表class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int: from collections import defaultdict def dfs(node, curr_sum): if not node: return 0 nonlocal count curr_sum += node.val count += prefix[curr_sum - targetSum] prefix[curr_sum] += 1 dfs(node.left, curr_sum) dfs(node.right, curr_sum) prefix[curr_sum] -= 1 prefix = defaultdict(int) prefix[0] = 1 # 初始前缀和为0出现1次 count = 0 dfs(root, 0) return count

4、复杂度分析

方法时间复杂度空间复杂度特点双重递归 O(n²) O(h) 简单直观但效率低前缀和+哈希表 O(n) O(n) 效率高，利用前缀和思想

Q49、二叉树的最近公共祖先

1、题目描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1输出：3解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4输出：5解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2输出：1
提示：

树中节点数目在范围 [2, 105] 内。

-109 <= Node.val <= 109

所有 Node.val 互不相同 。

p != q

p 和 q 均存在于给定的二叉树中。

2、解题思路

方法一：递归判断

基本情况：如果当前节点是 p 或 q，直接返回当前节点
查找子树：分别在左右子树中查找 p 和 q
判断位置 ：
- 如果 p 和 q 分别位于左右子树，当前节点就是 LCA
- 如果都在左子树，则在左子树中递归查找
- 如果都在右子树，则在右子树中递归查找
复杂度 ：
- 时间复杂度：O(n)，每个节点最多被访问一次
- 空间复杂度：O(h)，递归栈空间（h为树高）

方法二：哈希表记录父节点

构建父节点映射：通过遍历树，记录每个节点的父节点
回溯路径：从 p 开始回溯到根节点，标记访问过的节点
查找共同祖先：从 q 开始回溯，第一个被标记过的节点就是 LCA
复杂度 ：
- 时间复杂度：O(n)，需要遍历树两次
- 空间复杂度：O(n)，需要存储父节点映射和访问标记

3、代码实现

C++

// 方法1: 递归判断class Solution {public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { // 基本情况: 当前节点是 p 或 q, 直接返回 if (!root || root == p || root == q) { return root; } // 在左右子树中分别查找 p 和 q TreeNode* left = lowestCommonAncestor(root->left, p, q); TreeNode* right = lowestCommonAncestor(root->right, p, q); // 如果 p 和 q 分别位于左右子树, 当前节点就是 LCA if (left && right) { return root; } // 否则返回非空的那个子树结果 return left ? left : right; }};

// 方法2: 哈希表记录父亲节点class Solution {public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { unordered_map parent; // 父节点映射 unordered_set visited;  // 访问标记 // DFS 遍历树, 记录每个节点的父亲节点 stack s; s.push(root); parent[root] = nullptr; while (!s.empty()) { TreeNode* node = s.top(); s.pop(); if (node->left) { parent[node->left] = node; s.push(node->left); } if (node->right) { parent[node->right] = node; s.push(node->right); } } // 从 p 回溯到根节点, 标记路径上的节点 while (p) { visited.insert(p); p = parent[p]; } // 从 q 回溯到根节点, 找到第一个被标记的节点 while (q) { if (visited.count(q)) { return q; } q = parent[q]; } return nullptr; }};

Java

// 方法1: 递归判断class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) { return root; } TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left != null && right != null) { return root; } return left != null ? left : right; }}

Python

# 方法1: 递归判断class Solution: def lowestCommonAncestor( self, root: \"TreeNode\", p: \"TreeNode\", q: \"TreeNode\" ) -> \"TreeNode\": if not root or root == p or root == q: return root left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) if left and right: return root return left if left else right

4、复杂度分析

方法时间复杂度空间复杂度特点递归判断 O(n) O(h) 简洁高效，利用递归特性哈希表记录 O(n) O(n) 需要额外空间，但思路直观

Q50、二叉树中的最大路径和

1、题目描述

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

《LeetCode 热题 100》整整 100 题量大管饱题解套餐中

输入：root = [1,2,3]输出：6解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

《LeetCode 热题 100》整整 100 题量大管饱题解套餐中

输入：root = [-10,9,20,null,null,15,7]输出：42解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

树中节点数目范围是 [1, 3 * 104]
-1000 <= Node.val <= 1000

2、解题思路

方法：递归计算

核心思想：
- 对于每个节点，计算其作为路径\"转折点\"时的最大路径和（即左子树路径+当前节点+右子树路径）
- 同时计算该节点能提供的最大贡献值（即当前节点值加上左右子树中较大的贡献值）
- 全局维护一个最大路径和变量
关键点：
- 路径可以是从任意节点出发到任意节点结束
- 节点值可能为负，需要处理负贡献情况
- 递归过程需要返回当前节点的最大贡献值

3、代码实现

C++

class Solution {public: int maxPathSum(TreeNode* root) { maxGain(root); return maxSum; }private: int maxSum = INT_MIN; // 全局变量, 最大路径和 // 计算以 node 为起点的最大贡献值 int maxGain(TreeNode* node) { if (node == nullptr) { return 0; } // 递归计算左右子树的最大贡献值 int leftGain = max(maxGain(node->left), 0); // 如果贡献为负则舍弃 int rightGain = max(maxGain(node->right), 0); // 计算以当前节点为转折点的路径和 int priceNewpath = node->val + leftGain + rightGain; // 更新全局最大路径和 maxSum = max(maxSum, priceNewpath); // 返回当前节点的最大贡献值 (只能选择左右子树的一条路径) return node->val + max(leftGain, rightGain); }};

Java

class Solution { private int maxSum = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { maxGain(root); return maxSum; } private int maxGain(TreeNode node) { if (node == null) { return 0; } int leftGain = Math.max(maxGain(node.left), 0); int rightGain = Math.max(maxGain(node.right), 0); int newPathSum = node.val + leftGain + rightGain; maxSum = Math.max(maxSum, newPathSum); return node.val + Math.max(leftGain, rightGain); }}

Python

class Solution: def __init__(self): self.max_sum = float(\'-inf\') def maxPathSum(self, root: Optional[TreeNode]) -> int: def max_gain(node): if not node: return 0 left_gain = max(max_gain(node.left), 0) right_gain = max(max_gain(node.right), 0) new_path_sum = node.val + left_gain + right_gain self.max_sum = max(self.max_sum, new_path_sum) return node.val + max(left_gain, right_gain) max_gain(root) return self.max_sum

4、复杂度分析

时间复杂度：O(n)，每个节点访问一次
空间复杂度：O(h)，递归栈空间（h为树高）

9、图论

Q51、岛屿数量

1、题目描述

给你一个由 \'1\'（陆地）和 \'0\'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [[\"1\",\"1\",\"1\",\"1\",\"0\"],[\"1\",\"1\",\"0\",\"1\",\"0\"],[\"1\",\"1\",\"0\",\"0\",\"0\"],[\"0\",\"0\",\"0\",\"0\",\"0\"]]输出：1

示例 2：

输入：grid = [[\"1\",\"1\",\"0\",\"0\",\"0\"],[\"1\",\"1\",\"0\",\"0\",\"0\"],[\"0\",\"0\",\"1\",\"0\",\"0\"],[\"0\",\"0\",\"0\",\"1\",\"1\"]]输出：3

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 \'0\' 或 \'1\'

2、解题思路

方法一：深度优先搜索 (DFS)

核心思想：
- 遍历网格中的每个点
- 当遇到未访问的陆地(‘1’)时，启动DFS/BFS标记所有相连的陆地
- 每次启动DFS/BFS就代表发现了一个新岛屿
DFS特点：
- 递归实现
- 需要维护访问标记数组
- 空间复杂度主要取决于递归栈深度

方法二：广度优先搜索 (BFS)

核心思想：
- 与 DFS 类似，但使用队列实现
- 发现陆地后，使用队列进行层级扩展
- 可以原地修改网格来避免额外空间
BFS特点：
- 迭代实现
- 适合较大的网格（递归深度不会太深）
- 可以原地修改网格，空间效率更高

3、代码实现

C++

// 方法1: DFSclass Solution {private: const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; void dfs(vector<vector>& grid, vector<vector>& visited, int i, int j) { // 标记当前节点为已访问 visited[i][j] = true; // 遍历四个方向 for (const auto& dir : dirs) { int x = i + dir[0]; int y = j + dir[1]; // 检查边界条件和是否未访问的陆地 if (x >= 0 && x = 0 && y < grid[0].size() && grid[x][y] == \'1\' && !visited[x][y]) { dfs(grid, visited, x, y); } } }public: int numIslands(vector<vector>& grid) { if (grid.empty() || grid[0].empty()) { return 0; } int m = grid.size(), n = grid[0].size(); vector<vector> visited(m, vector(n, false)); int count = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == \'1\' && !visited[i][j]) {  ++count;  dfs(grid, visited, i, j); } } } return count; }};

// 方法2: BFSclass Solution {public: int numIslands(vector<vector>& grid) { if (grid.empty() || grid[0].empty()) { return 0; } int m = grid.size(), n = grid[0].size(); int count = 0; const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == \'1\') {  ++count;  grid[i][j] = \'0\'; // 标记为已访问  queue<pair> q;  q.push({i, j});  while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (const auto& dir : dirs) { int nx = x + dir[0]; int ny = y + dir[1]; if (nx >= 0 && nx = 0 && ny < n && grid[nx][ny] == \'1\') { grid[nx][ny] = \'0\'; q.push({nx, ny}); } }  } } } } return count; }};

Java

// 方法2: BFSclass Solution { private static final int[][] dirs = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }; public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) { return 0; } int m = grid.length, n = grid[0].length; boolean[][] visited = new boolean[m][n]; int count = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == \'1\' && !visited[i][j]) {  count++;  dfs(grid, visited, i, j); } } } return count; } private void dfs(char[][] grid, boolean[][] visited, int i, int j) { visited[i][j] = true; for (int[] dir : dirs) { int x = i + dir[0]; int y = j + dir[1]; if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] == \'1\' && !visited[x][y]) { dfs(grid, visited, x, y); } } }}

Python

# 方法2: BFSclass Solution: def numIslands(self, grid: List[List[str]]) -> int: if not grid: return 0 m, n = len(grid), len(grid[0]) count = 0 def dfs(i, j): if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != \'1\': return grid[i][j] = \'0\' # 标记为已访问 # 四个方向递归 dfs(i-1, j) dfs(i+1, j) dfs(i, j-1) dfs(i, j+1) for i in range(m): for j in range(n): if grid[i][j] == \'1\':  count += 1  dfs(i, j) return count

4、复杂度分析

方法时间复杂度空间复杂度特点 DFS O(M×N) O(M×N) 递归实现，需要额外空间记录访问状态 BFS O(M×N) O(min(M,N)) 迭代实现，可以原地修改网格

Q52、腐烂的橘子

1、题目描述

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

示例 1：

输入：grid = [[2,1,1],[1,1,0],[0,1,1]]输出：4

示例 2：

输入：grid = [[2,1,1],[0,1,1],[1,0,1]]输出：-1解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。

示例 3：

输入：grid = [[0,2]]输出：0解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 10
grid[i][j] 仅为 0、1 或 2

2、解题思路

方法：多源广度优先搜索 (BFS)

核心思想：
- 将所有腐烂橘子作为初始源点，同时开始BFS
- 每一轮扩展腐烂橘子的影响范围
- 记录扩展所需的轮数（分钟数）
- 最后检查是否所有新鲜橘子都被腐烂
关键点：
- 使用队列存储所有初始腐烂橘子的位置
- 每一轮处理当前队列中的所有橘子
- 使用标记数组或直接修改原网格来记录橘子状态

3、代码实现

C++

class Solution {private: // 四个方向: 右、左、上、下 const int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};public: int orangesRotting(vector<vector>& grid) { if (grid.empty() || grid[0].empty()) { return 0; } int m = grid.size(), n = grid[0].size(); queue<pair> q; int fresh = 0; // 记录新鲜橘子数量 // 初始化队列并统计新鲜橘子 for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == 2) {  q.push({i, j}); } else if (grid[i][j] == 1) {  ++fresh; } } } // 如果没有新鲜橘子, 直接返回 0 if (fresh == 0) { return 0; } int minutes = 0; while (!q.empty()) { int size = q.size(); bool infected = false; // 标记本轮是否有句子被感染 for (int i = 0; i = 0 && nx = 0 && ny < n && grid[nx][ny] == 1) { grid[nx][ny] = 2; q.push({nx, ny}); --fresh; infected = true;  } } } if (infected) { ++minutes; } } return fresh == 0 ? minutes : -1; }};

Java

class Solution { private static final int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } }; public int orangesRotting(int[][] grid) { if (grid == null || grid.length == 0) { return 0; } int m = grid.length, n = grid[0].length; Queue<int[]> queue = new LinkedList<>(); int fresh = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 2) {  queue.offer(new int[] { i, j }); } else if (grid[i][j] == 1) {  fresh++; } } } if (fresh == 0) { return 0; } int minutes = 0; while (!queue.isEmpty()) { int size = queue.size(); boolean infected = false; for (int i = 0; i < size; i++) { int[] pos = queue.poll(); for (int[] dir : dirs) {  int x = pos[0] + dir[0];  int y = pos[1] + dir[1];  if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) { grid[x][y] = 2; queue.offer(new int[] { x, y }); fresh--; infected = true;  } } } if (infected) { minutes++; } } return fresh == 0 ? minutes : -1; }}

Python

class Solution: def orangesRotting(self, grid: List[List[int]]) -> int: if not grid: return 0 m, n = len(grid), len(grid[0]) queue = deque() fresh = 0 for i in range(m): for j in range(n): if grid[i][j] == 2:  queue.append((i, j)) elif grid[i][j] == 1:  fresh += 1 if fresh == 0: return 0 minutes = 0 dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)] while queue: size = len(queue) infected = False for _ in range(size): x, y = queue.popleft() for dx, dy in dirs:  nx, ny = x + dx, y + dy  if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1: grid[nx][ny] = 2 queue.append((nx, ny)) fresh -= 1 infected = True if infected: minutes += 1 return minutes if fresh == 0 else -1

4、复杂度分析

时间复杂度：O(mn)，每个节点最多被访问一次
空间复杂度：O(mn)，最坏情况下队列需要存储所有橘子位置

Q53、课程表

1、题目描述

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则必须先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]输出：true解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]输出：false解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
提示：

1 <= numCourses <= 2000

0 <= prerequisites.length <= 5000

prerequisites[i].length == 2

0 <= ai, bi < numCourses

prerequisites[i] 中的所有课程对 互不相同

2、解题思路

方法一：深度优先搜索 (DFS) 检测环

核心思想：
- 将课程关系建模为有向图
- 使用 DFS 检测图中是否存在环
- 存在环则无法完成所有课程
关键点：
- 三种状态标记：未访问(0)、访问中(1)、已访问(2)
- 遇到访问中的节点表示发现环

方法二：拓扑排序 (BFS)

核心思想：
- 计算每个节点的入度
- 从入度为0的节点开始BFS
- 每次移除节点并减少相邻节点的入度
- 最终判断是否所有节点都被访问
关键点：
- 使用队列存储当前入度为0的节点
- 维护入度表和邻接表

3、代码实现

C++

// 方法1: DFSclass Solution {private: vector<vector> edges; // 邻接表 vector visited; // 访问状态: 0 未访问, 1 访问中, 2 已访问 bool valid = true; // 是否有效 (无环) void dfs(int u) { visited[u] = 1; // 标记为访问中 for (int v : edges[u]) { // 遇到未访问节点, 继续 DFS if (visited[v] == 0) { dfs(v); if (!valid) {  return; } } // 遇到访问中节点, 发现环 else if (visited[v] == 1) { valid = false; return; } } visited[u] = 2; // 标记为已访问 }public: bool canFinish(int numCourses, vector<vector>& prerequisites) { edges.resize(numCourses); visited.resize(numCourses); // 构建邻接表 for (const auto& p : prerequisites) { edges[p[1]].push_back(p[0]); } // 对每个未访问节点进行 DFS for (int i = 0; i < numCourses && valid; ++i) { if (visited[i] == 0) { dfs(i); } } return valid; }};

// 方法2: 拓扑排序 (BFS)class Solution {public: bool canFinish(int numCourses, vector<vector>& prerequisites) { vector<vector> edges(numCourses); // 邻接表 vector indeg(numCourses); // 入度表 // 构建邻接表和入度表 for (const auto& p : prerequisites) { edges[p[1]].push_back(p[0]); indeg[p[0]]++; } queue q; // 将入度为 0 的节点加入队列 for (int i = 0; i < numCourses; ++i) { if (indeg[i] == 0) { q.push(i); } } int visited = 0; // 已访问节点数 while (!q.empty()) { int u = q.front(); q.pop(); visited++; // 减少邻接节点的入度 for (int v : edges[u]) { indeg[v]--; if (indeg[v] == 0) {  q.push(v); } } } return visited == numCourses; }};

Java

class Solution { private List<List<Integer>> edges; private int[] visited; private boolean valid = true; public boolean canFinish(int numCourses, int[][] prerequisites) { edges = new ArrayList<>(); for (int i = 0; i < numCourses; i++) { edges.add(new ArrayList<>()); } visited = new int[numCourses]; for (int[] p : prerequisites) { edges.get(p[1]).add(p[0]); } for (int i = 0; i < numCourses && valid; i++) { if (visited[i] == 0) { dfs(i); } } return valid; } private void dfs(int u) { visited[u] = 1; for (int v : edges.get(u)) { if (visited[v] == 0) { dfs(v); if (!valid) {  return; } } else if (visited[v] == 1) { valid = false; return; } } visited[u] = 2; }}

Python

class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: edges = [[] for _ in range(numCourses)] indeg = [0] * numCourses for p in prerequisites: edges[p[1]].append(p[0]) indeg[p[0]] += 1 q = deque([i for i in range(numCourses) if indeg[i] == 0]) visited = 0 while q: u = q.popleft() visited += 1 for v in edges[u]: indeg[v] -= 1 if indeg[v] == 0:  q.append(v) return visited == numCourses

4、复杂度分析

方法时间复杂度空间复杂度特点 DFS O(V+E) O(V+E) 需要构建邻接表，递归深度可能较大 BFS O(V+E) O(V+E) 更适合大规模数据，迭代实现

Q54、实现 Trie (前缀树)

1、题目描述

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

输入[\"Trie\", \"insert\", \"search\", \"search\", \"startsWith\", \"insert\", \"search\"][[], [\"apple\"], [\"apple\"], [\"app\"], [\"app\"], [\"app\"], [\"app\"]]输出[null, null, true, false, true, null, true]解释Trie trie = new Trie();trie.insert(\"apple\");trie.search(\"apple\"); // 返回 Truetrie.search(\"app\"); // 返回 Falsetrie.startsWith(\"app\"); // 返回 Truetrie.insert(\"app\");trie.search(\"app\"); // 返回 True

提示：

1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数总计不超过 3 * 104 次

2、解题思路

Trie是一种树形数据结构，用于高效存储和检索字符串。每个节点包含：

子节点指针数组（26个对应小写字母）
结束标志位（标记是否为一个完整单词的结尾）

核心操作

插入：沿着字符串字符逐个创建/访问节点
搜索：检查是否能完整遍历字符串路径且结尾标记为true
前缀搜索：只需检查是否能遍历完前缀路径

3、代码实现

C++

class Trie {private: vector children; // 26 个子节点指针 bool isEnd; // 是否单词结尾 // 搜索前缀辅助函数 Trie* searchPrefix(string prefix) { Trie* node = this; for (char ch : prefix) { ch -= \'a\'; // 字符转索引 if (!node->children[ch]) { return nullptr; } node = node->children[ch]; } return node; } void clear(Trie* node) { for (auto& child : node->children) { if (child) { clear(child); delete child; child = nullptr; } } }public: Trie() : children(26), isEnd(false) {} void insert(string word) { Trie* node = this; for (char ch : word) { ch -= \'a\'; if (!node->children[ch]) { node->children[ch] = new Trie(); } node = node->children[ch]; } node->isEnd = true; // 标记单词结尾 } bool search(string word) { Trie* node = searchPrefix(word); return node && node->isEnd; // 必须完整单词 } bool startsWith(string prefix) { return searchPrefix(prefix) != nullptr; // 只需前缀存在 } // 内存清理 ~Trie() { clear(this); }};

Java

class Trie { private Trie[] children; // 子节点数组 private boolean isEnd; // 结束标志 public Trie() { children = new Trie[26]; isEnd = false; } public void insert(String word) { Trie node = this; for (char ch : word.toCharArray()) { int idx = ch - \'a\'; if (node.children[idx] == null) { node.children[idx] = new Trie(); } node = node.children[idx]; } node.isEnd = true; // 设置单词结尾 } public boolean search(String word) { Trie node = searchPrefix(word); return node != null && node.isEnd; // 完整单词判断 } public boolean startsWith(String prefix) { return searchPrefix(prefix) != null; // 前缀存在判断 } private Trie searchPrefix(String prefix) { Trie node = this; for (char ch : prefix.toCharArray()) { int idx = ch - \'a\'; if (node.children[idx] == null) { return null; } node = node.children[idx]; } return node; }}

Python

class TrieNode: def __init__(self): self.children = {} # 字典存储子节点 self.is_end = False # 单词结束标志class Trie: def __init__(self): self.root = TrieNode() # 根节点 def insert(self, word: str) -> None: node = self.root for ch in word: if ch not in node.children: # 不存在则创建 node.children[ch] = TrieNode() node = node.children[ch] # 移动到子节点 node.is_end = True # 标记单词结束 def search(self, word: str) -> bool: node = self.search_prefix(word) return node is not None and node.is_end # 需完整匹配 def startsWith(self, prefix: str) -> bool: return self.search_prefix(prefix) is not None # 只需前缀存在 def search_prefix(self, prefix: str) -> TrieNode: node = self.root for ch in prefix: if ch not in node.children: # 前缀不匹配 return None node = node.children[ch] return node

4、复杂度分析

操作时间复杂度空间复杂度插入 O(L) O(L) 搜索 O(L) O(1) 前缀 O(L) O(1)

其中L是单词/前缀长度

10、回溯

Q55、全排列

1、题目描述

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：
输入：nums = [1,2,3]输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]输出：[[1]]
提示：

1 <= nums.length <= 6

-10 <= nums[i] <= 10

nums 中的所有整数 互不相同

2、解题思路

回溯算法

使用回溯算法系统地遍历所有可能的排列组合。核心思想是：

选择一个未被使用的数字加入当前路径
标记该数字为已使用
递归处理剩余数字
回溯（撤销选择，恢复状态）

关键点

使用一个标记数组 check 记录哪些数字已被使用
当路径长度等于原数组长度时，得到一个有效排列
通过回溯恢复状态，使得每个数字都有机会出现在每个位置

3、代码实现

C++

class Solution {private: vector<vector> ret; // 存储所有排列结果 vector path; // 当前路径 bool check[7];  // 标记数组, 记录数字是否已经使用 void dfs(vector& nums) { // 当路径长度等于数组长度, 得到一个完整排列 if (nums.size() == path.size()) { ret.push_back(path); return; } // 遍历所有数字 for (int i = 0; i < nums.size(); ++i) { // 如果该数字未被使用 if (!check[i]) { path.push_back(nums[i]); // 加入当前路径 check[i] = true; // 标记为已使用 dfs(nums);  // 递归处理 // 回溯: 恢复状态 path.pop_back(); check[i] = false; } } }public: vector<vector> permute(vector& nums) { dfs(nums); return ret; }};

Java

class Solution { private List<List<Integer>> ret = new ArrayList<>(); private List<Integer> path = new ArrayList<>(); private boolean[] check; private void dfs(int[] nums) { if (path.size() == nums.length) { ret.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; i++) { if (!check[i]) { path.add(nums[i]); check[i] = true; dfs(nums); // 回溯 path.remove(path.size() - 1); check[i] = false; } } } public List<List<Integer>> permute(int[] nums) { check = new boolean[nums.length]; dfs(nums); return ret; }}

Python

class Solution: def permute(self, nums: List[int]) -> List[List[int]]: def backtrack(path, used): if len(path) == len(nums): res.append(path[:]) # 添加当前排列的副本 return for i in range(len(nums)): if not used[i]:  path.append(nums[i])  used[i] = True  backtrack(path, used)  # 回溯  path.pop()  used[i] = False res = [] backtrack([], [False] * len(nums)) return res

4、复杂度分析

时间复杂度：O(n*n!)，共有 n! 种排列，每种排列需要 O(n) 时间构建
空间复杂度：O(n)，递归栈深度和标记数组的空间消耗

Q56、子集

1、题目描述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

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

示例 2：

输入：nums = [0]输出：[[],[0]]

2、解题思路

方法一：递归回溯

对于每个元素，有两种选择：包含或不包含在当前子集中
递归处理这两种情况
当处理完所有元素时，记录当前子集

方法二：迭代回溯

从空集开始构建
每次处理一个新元素时，将其加入现有的所有子集
生成新的子集并保留原有子集

3、代码实现

C++

// 方法1: 递归回溯class Solution {private: vector<vector> ret; // 存储所有子集结果 vector path; // 当前路径 void dfs(vector& nums, int pos) { // 处理完所有元素 if (pos == nums.size()) { ret.push_back(path); // 记录当前子集 return; } // 选择当前元素 path.push_back(nums[pos]); dfs(nums, pos + 1); // 不选当前元素 (回溯) path.pop_back(); dfs(nums, pos + 1); }public: vector<vector> subsets(vector& nums) { dfs(nums, 0); return ret; }};

// 方法2: 迭代回溯class Solution {private: vector<vector> ret; vector path; void dfs(vector& nums, int pos) { ret.push_back(path); // 每次递归都记录当前路径 for (int i = pos; i < nums.size(); ++i) { path.push_back(nums[i]); // 包含当前元素 dfs(nums, i + 1); // 递归处理后续元素 path.pop_back(); // 回溯 } }public: vector<vector> subsets(vector& nums) { dfs(nums, 0); return ret; }};

Java

class Solution { private List<List<Integer>> res = new ArrayList<>(); private List<Integer> path = new ArrayList<>(); private void dfs(int[] nums, int pos) { if (pos == nums.length) { res.add(new ArrayList<>(path)); return; } // 选择当前元素 path.add(nums[pos]); dfs(nums, pos + 1); // 不选当前元素 path.remove(path.size() - 1); dfs(nums, pos + 1); } public List<List<Integer>> subsets(int[] nums) { dfs(nums, 0); return res; }}

class Solution { private List<List> res = new ArrayList(); private List path = new ArrayList(); private void dfs(int[] nums, int pos) { res.add(new ArrayList(path)); // 添加当前子集 for (int i = pos; i < nums.length; i++) { path.add(nums[i]); dfs(nums, i + 1); path.remove(path.size() - 1); // 回溯 } } public List<List> subsets(int[] nums) { dfs(nums, 0); return res; }}

Python

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: def backtrack(pos): if pos == len(nums): res.append(path.copy()) return # 选择当前元素 path.append(nums[pos]) backtrack(pos + 1) # 不选当前元素 path.pop() backtrack(pos + 1) res = [] path = [] backtrack(0) return res

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: def backtrack(start, path): res.append(path.copy()) for i in range(start, len(nums)): path.append(nums[i]) backtrack(i + 1, path) path.pop() res = [] backtrack(0, []) return res

4、复杂度分析

时间复杂度：O(n * 2^n)，共有 2^n 个子集，每个子集平均需要 O(n) 时间构建
空间复杂度：O(n)，递归栈深度和路径存储的空间消耗

Q57、电话号码的字母组合

1、题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

《LeetCode 热题 100》整整 100 题量大管饱题解套餐中

示例 1：
输入：digits = \"23\"输出：[\"ad\",\"ae\",\"af\",\"bd\",\"be\",\"bf\",\"cd\",\"ce\",\"cf\"]
示例 2：
输入：digits = \"\"输出：[]
示例 3：
输入：digits = \"2\"输出：[\"a\",\"b\",\"c\"]
提示：

0 <= digits.length <= 4

digits[i] 是范围 [\'2\', \'9\'] 的一个数字。

2、解题思路

回溯算法

建立映射：将每个数字映射到对应的字母集合
回溯构建：对于每个数字，递归尝试所有可能的字母组合
终止条件：当当前路径长度等于输入数字串长度时，记录结果

关键点

使用哈希表存储数字到字母的映射
通过回溯遍历所有可能的字母组合
处理空输入的特殊情况

3、代码实现

C++

class Solution {private: const string hash[10] = {\"\", \"\", \"abc\", \"def\", \"ghi\", \"jkl\", \"mno\", \"pqrs\", \"tuv\", \"wxyz\"}; string path; // 当前组和路径 vector ret; // 存储所有结果 void dfs(const string& digits, int pos) { // 当组合长度等于数字串长度, 记录结果 if (pos == digits.size()) { ret.push_back(path); return; } // 获取当前数字对应的字母集合 const string& letters = hash[digits[pos] - \'0\']; // 遍历所有可能的字母 for (char ch : letters) { path.push_back(ch); // 选择当前字母 dfs(digits, pos + 1); // 递归处理下一个数字 path.pop_back(); // 回溯, 撤销选择 } }public: vector letterCombinations(string digits) { if (digits.empty()) { return {}; } dfs(digits, 0); return ret; }};

Java

class Solution { private static final String[] MAP = { \"\", \"\", \"abc\", \"def\", \"ghi\", \"jkl\", \"mno\", \"pqrs\", \"tuv\", \"wxyz\" }; private List<String> res = new ArrayList<>(); private StringBuilder path = new StringBuilder(); private void backtrack(String digits, int pos) { if (pos == digits.length()) { res.add(path.toString()); return; } String letters = MAP[digits.charAt(pos) - \'0\']; for (char c : letters.toCharArray()) { path.append(c); backtrack(digits, pos + 1); path.deleteCharAt(path.length() - 1); // 回溯 } } public List<String> letterCombinations(String digits) { if (digits.isEmpty()) { return res; } backtrack(digits, 0); return res; }}

Python

class Solution: def letterCombinations(self, digits: str) -> List[str]: if not digits: return [] digit_map = { \'2\': \'abc\', \'3\': \'def\', \'4\': \'ghi\', \'5\': \'jkl\', \'6\': \'mno\', \'7\': \'pqrs\', \'8\': \'tuv\', \'9\': \'wxyz\' } res = [] def backtrack(index, path): if index == len(digits): res.append(\'\'.join(path)) return for letter in digit_map[digits[index]]: path.append(letter) backtrack(index + 1, path) path.pop() # 回溯 backtrack(0, []) return res

4、复杂度分析

时间复杂度：O(3^N × 4^M)，其中N是对应3个字母的数字个数，M是对应4个字母的数字个数
空间复杂度：O(N)，递归调用栈的深度

Q58、组合总和

1、题目描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：
输入：candidates = [2,3,6,7], target = 7输出：[[2,2,3],[7]]解释：2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。7 也是一个候选， 7 = 7 。仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1输出: []
提示：

1 <= candidates.length <= 30

2 <= candidates[i] <= 40

candidates 的所有元素 互不相同

1 <= target <= 40

2、解题思路

回溯算法

选择与回溯：对于每个候选数字，选择它并递归处理剩余目标值
终止条件 ：
- 目标值为0：记录有效组合
- 目标值为负：剪枝，无效路径
避免重复组合：通过控制遍历起始位置(pos)保证组合顺序

关键点

排序数组可以优化剪枝（但本题未排序也可）
使用pos参数确保不会产生顺序不同但元素相同的重复组合
允许重复选择同一数字：递归时传入i而非i+1

3、代码实现

C++

// 方法1: 简洁回溯class Solution {private: vector<vector> ret; vector path; void dfs(vector& candidates, int pos, int target) { // 找到有效组合 if (target == 0) { ret.push_back(path); return; } // 剪枝 if (target < 0) { return; } for (int i = pos; i < candidates.size(); ++i) { path.push_back(candidates[i]);  // 选择当前数字 dfs(candidates, i, target - candidates[i]); // 允许重复选择 path.pop_back(); // 回溯 } }public: vector<vector> combinationSum(vector& candidates, int target) { dfs(candidates, 0, target); return ret; }};

// 方法2: 带当前和的回溯class Solution {public: vector<vector> combinationSum(vector& candidates, int target) { vector<vector> solutions; vector solution; dfs(solutions, solution, 0, 0, target, candidates); return solutions; } void dfs(vector<vector>& solutions, vector& solution, int curSum, int preIdx, int target, vector& candidates) { if (curSum >= target) // 终止条件 { if (curSum == target) { solutions.push_back(solution); } return; } for (int i = preIdx; i < candidates.size(); ++i) { solution.push_back(candidates[i]); // 允许重复选择, 传入 i 而非 i+1 dfs(solutions, solution, curSum + candidates[i], i, target, candidates); solution.pop_back(); // 回溯 } }};

Java

class Solution { private List<List<Integer>> res = new ArrayList<>(); private List<Integer> path = new ArrayList<>(); private void dfs(int[] candidates, int start, int target) { if (target == 0) { res.add(new ArrayList<>(path)); return; } if (target < 0) { return; } for (int i = start; i < candidates.length; i++) { path.add(candidates[i]); dfs(candidates, i, target - candidates[i]); // 允许重复 path.remove(path.size() - 1); // 回溯 } } public List<List<Integer>> combinationSum(int[] candidates, int target) { dfs(candidates, 0, target); return res; }}

Python

class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: def backtrack(start, path, target): if target == 0: res.append(path.copy()) return if target < 0: return for i in range(start, len(candidates)): path.append(candidates[i]) backtrack(i, path, target - candidates[i]) # 允许重复 path.pop() # 回溯 res = [] backtrack(0, [], target) return res

4、复杂度分析

时间复杂度：O(S)，其中S是所有可行解的长度之和
空间复杂度：O(target)，递归栈深度

Q59、括号生成

1、题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3输出：[\"((()))\",\"(()())\",\"(())()\",\"()(())\",\"()()()\"]

示例 2：

输入：n = 1输出：[\"()\"]

提示：

1 <= n <= 8

2、解题思路

回溯算法

跟踪括号数量：维护当前左括号和右括号的数量
有效性条件 ：
- 左括号数不超过n
- 右括号数不超过左括号数
终止条件：当右括号数达到n时，记录当前组合

关键点

确保在任何位置右括号数不超过左括号数
通过递归回溯探索所有可能组合
剪枝无效路径（右括号多于左括号的情况）

3、代码实现

C++

class Solution {public: vector generateParenthesis(int n) { vector ret; // 存储所有有效组合 string path; // 当前路径 dfs(ret, path, 0, 0, n); // 初始左右括号都为 0 return ret; } void dfs(vector& ret, string& path, int left, int right, int n) { // 当右括号达到 n 对, 记录有效组合 if (right == n) { ret.push_back(path); return; } // 可以添加左括号条件: 左括号数小于 n if (left < n) { path.push_back(\'(\'); dfs(ret, path, left + 1, right, n); path.pop_back(); // 回溯 } // 可以添加右括号的条件: 右括号数小于左括号数 if (right < left) { path.push_back(\')\'); dfs(ret, path, left, right + 1, n); path.pop_back(); // 回溯 } }};

Java

class Solution { public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<>(); backtrack(res, new StringBuilder(), 0, 0, n); return res; } private void backtrack(List<String> res, StringBuilder path, int left, int right, int n) { if (right == n) { res.add(path.toString()); return; } if (left < n) { path.append(\'(\'); backtrack(res, path, left + 1, right, n); path.deleteCharAt(path.length() - 1); // 回溯 } if (right < left) { path.append(\')\'); backtrack(res, path, left, right + 1, n); path.deleteCharAt(path.length() - 1); // 回溯 } }}

Python

class Solution: def generateParenthesis(self, n: int) -> List[str]: def backtrack(path, left, right): if right == n: res.append(\'\'.join(path)) return if left < n: path.append(\'(\') backtrack(path, left + 1, right) path.pop() # 回溯 if right < left: path.append(\')\') backtrack(path, left, right + 1) path.pop() # 回溯 res = [] backtrack([], 0, 0) return res

4、复杂度分析

时间复杂度：O(4^n/√n)，这是第n个卡特兰数的渐近界
空间复杂度：O(n)，递归栈深度和路径存储的空间消耗

Q60、单词搜索

1、题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：
输入：board = [[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]], word = \"ABCCED\"输出：true
示例 2：
输入：board = [[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]], word = \"SEE\"输出：true
示例 3：
输入：board = [[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]], word = \"ABCB\"输出：false
提示：

m == board.length

n = board[i].length

1 <= m, n <= 6

1 <= word.length <= 15

board 和 word 仅由大小写英文字母组成

**进阶：**你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

2、解题思路

回溯算法

遍历起点：从网格中每个与单词首字母匹配的单元格开始
深度优先搜索：向四个方向递归搜索
剪枝条件：
- 超出边界
- 已访问过
- 当前字符不匹配
终止条件：匹配完整个单词

3、代码实现

C++

class Solution {private: const int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; bool dfs(vector<vector>& board, string& word, vector<vector>& visited, int i, int j, int pos) { // 匹配完成 if (pos == word.size()) { return true; } for (int k = 0; k = 0 && x = 0 && y < board[0].size() && !visited[x][y] && board[x][y] == word[pos]) { visited[x][y] = true; if (dfs(board, word, visited, x, y, pos + 1)) {  return true; } visited[x][y] = false; // 回溯 } } return false; }public: bool exist(vector<vector>& board, string word) { int m = board.size(), n = board[0].size(); vector<vector> visited(m, vector(n, false)); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (board[i][j] == word[0]) // 找到可能的起点 {  visited[i][j] = true;  if (dfs(board, word, visited, i, j, 1)) { return true;  }  visited[i][j] = false; // 回溯 } } } return false; }};

Java

class Solution { private static final int[][] DIR = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }; private boolean dfs(char[][] board, String word, boolean[][] visited, int i, int j, int pos) { if (pos == word.length()) { return true; } for (int[] d : DIR) { int x = i + d[0]; int y = j + d[1]; if (x >= 0 && x < board.length && y >= 0 && y < board[0].length && !visited[x][y] && board[x][y] == word.charAt(pos)) { visited[x][y] = true; if (dfs(board, word, visited, x, y, pos + 1)) {  return true; } visited[x][y] = false; } } return false; } public boolean exist(char[][] board, String word) { int m = board.length, n = board[0].length; boolean[][] visited = new boolean[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == word.charAt(0)) {  visited[i][j] = true;  if (dfs(board, word, visited, i, j, 1)) { return true;  }  visited[i][j] = false; } } } return false; }}

Python

class Solution: def exist(self, board: List[List[str]], word: str) -> bool: def dfs(i, j, pos): if pos == len(word): return True for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]: x, y = i + dx, j + dy if 0 <= x < m and 0 <= y < n and not visited[x][y] and board[x][y] == word[pos]:  visited[x][y] = True  if dfs(x, y, pos + 1): return True  visited[x][y] = False return False m, n = len(board), len(board[0]) visited = [[False]*n for _ in range(m)] for i in range(m): for j in range(n): if board[i][j] == word[0]:  visited[i][j] = True  if dfs(i, j, 1): return True  visited[i][j] = False return False

4、复杂度分析

时间复杂度：O(M×N×3^L)，其中M×N是网格大小，L是单词长度
空间复杂度：O(L)，递归栈深度和visited数组的空间消耗

Q61、分割回文串

1、题目描述

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：
输入：s = \"aab\"输出：[[\"a\",\"a\",\"b\"],[\"aa\",\"b\"]]
示例 2：
输入：s = \"a\"输出：[[\"a\"]]
提示：

1 <= s.length <= 16

s 仅由小写英文字母组成

2、解题思路

两种主要方法

动态规划预处理+回溯：
- 先用动态规划预处理所有可能的回文子串
- 然后通过回溯生成所有分割方案
记忆化搜索+回溯：
- 在回溯过程中实时判断回文
- 使用记忆化技术避免重复计算

3、代码实现

C++

class Solution {private: vector<vector> dp; // dp[i][j] 表示 s[i...j] 是否是回文 vector<vector> ret; // 存储所有结果 vector ans; // 当前分割方案 int n;// 字符串长度 // 回溯生成所有分割方案 void dfs(const string& s, int i) { // 分割完成 if (i == n) { ret.push_back(ans); return; } for (int j = i; j < n; ++j) { // 如果是回文 if (dp[i][j]) { ans.push_back(s.substr(i, j - i + 1)); // 加入当前方案 dfs(s, j + 1); // 继续处理剩余部分 ans.pop_back(); // 回溯 } } }public: vector<vector> partition(string s) { n = s.size(); dp.assign(n, vector(n, true)); // 初始化 dp 数组 // 动态规划预处理所有回文子串 for (int i = n - 1; i >= 0; --i) { for (int j = i + 1; j < n; ++j) { dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1]; } } dfs(s, 0); // 从第 0 个字符开始回溯 return ret; }};

class Solution {private: vector<vector> dp; // 记忆化数组 vector<vector> ret; // 存储所有结果 vector ans; // 当前分割方案 int n;// 字符串长度 // 回溯生成所有分割方案 void dfs(const string& s, int i) { // 分割完成 if (i == n) { ret.push_back(ans); return; } for (int j = i; j = j) { return dp[i][j] = true; // 单个字符或空串 } return dp[i][j] = (s[i] == s[j]) ? isPalindrome(s, i + 1, j - 1) : false; }public: vector<vector> partition(string s) { n = s.size(); dp.assign(n, vector(n, false)); // 初始化记忆化数组 dfs(s, 0); // 从第 0 个字符开始回溯 return ret; }};

Java

class Solution { private List<List<String>> res = new ArrayList<>(); private List<String> path = new ArrayList<>(); private boolean[][] dp; private int n; public List<List<String>> partition(String s) { n = s.length(); dp = new boolean[n][n]; // 预处理回文子串 for (int i = n - 1; i >= 0; i--) { for (int j = i; j < n; j++) { if (i == j) {  dp[i][j] = true; } else if (j == i + 1) {  dp[i][j] = s.charAt(i) == s.charAt(j); } else {  dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]; } } } backtrack(s, 0); return res; } private void backtrack(String s, int start) { if (start == n) { res.add(new ArrayList<>(path)); return; } for (int end = start; end < n; end++) { if (dp[start][end]) { path.add(s.substring(start, end + 1)); backtrack(s, end + 1); path.remove(path.size() - 1); } } }}

Python

class Solution: def partition(self, s: str) -> List[List[str]]: n = len(s) dp = [[False]*n for _ in range(n)] res = [] # 预处理回文子串 for i in range(n-1, -1, -1): for j in range(i, n): if i == j:  dp[i][j] = True elif j == i + 1:  dp[i][j] = s[i] == s[j] else:  dp[i][j] = s[i] == s[j] and dp[i+1][j-1] def backtrack(start, path): if start == n: res.append(path.copy()) return for end in range(start, n): if dp[start][end]:  path.append(s[start:end+1])  backtrack(end+1, path)  path.pop() backtrack(0, []) return res

4、复杂度分析

方法一：动态规划预处理+回溯

时间复杂度：O(n2ⁿ)，预处理O(n²)，回溯O(n2ⁿ)
空间复杂度：O(n²)，存储dp数组

方法二：记忆化搜索+回溯

时间复杂度：O(n*2ⁿ)
空间复杂度：O(n²)

Q62、N 皇后

1、题目描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 \'Q\' 和 \'.\' 分别代表了皇后和空位。

示例 1：

《LeetCode 热题 100》整整 100 题量大管饱题解套餐中

输入：n = 4输出：[[\".Q..\",\"...Q\",\"Q...\",\"..Q.\"],[\"..Q.\",\"Q...\",\"...Q\",\".Q..\"]]解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1输出：[[\"Q\"]]

提示：

1 <= n <= 9

2、解题思路

数组标记法：
- 使用三个数组分别标记列和两条对角线的占用情况
- 通过回溯生成所有合法方案
位置验证法：
- 实时验证每个位置是否与已放置的皇后冲突
- 同样使用回溯生成所有方案

3、代码实现

C++

// 方法1: 数组标记法class Solution {private: bool col[10] = {false}; // 标记列是否被占用 bool diag1[20] = {false}; // 标记主对角线 (左上到右下) 是否被占用 bool diag2[20] = {false}; // 标记副对角线 (右上到左下) 是否被占用 vector<vector> res; // 存储所有结果 vector board; // 当前棋盘状态 int n;// 棋盘大小 void backtrack(int row) { // 找到一个解 if (row == n) { res.push_back(board); return; } for (int c = 0; c < n; ++c) { // 检查当前位置是否可用 if (!col[c] && !diag1[row - c + n] && !diag2[row + c]) { // 放置皇后 board[row][c] = \'Q\'; col[c] = diag1[row - c + n] = diag2[row + c] = true; // 递归下一行 backtrack(row + 1); // 回溯 board[row][c] = \'.\'; col[c] = diag1[row - c + n] = diag2[row + c] = false; } } }public: vector<vector> solveNQueens(int n) { this->n = n; board.resize(n, string(n, \'.\')); // 初始化空棋盘 backtrack(0); return res; }};

// 方法2: 位置验证法class Solution {private: vector<vector> res; // 存储所有结果 // 验证当前位置是否合法 bool isValid(vector& board, int row, int col) { int n = board.size(); // 检查列 for (int i = 0; i = 0 && j >= 0; --i, --j) { if (board[i][j] == \'Q\') { return false; } } // 检查右上对角线 for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) { if (board[i][j] == \'Q\') { return false; } } return true; } void backtrack(vector& board, int row) { // 找到一个解 if (row == board.size()) { res.push_back(board); return; } for (int col = 0; col < board.size(); col++) { // 如果位置合法 if (isValid(board, row, col)) { board[row][col] = \'Q\'; // 放置皇后 backtrack(board, row + 1); // 处理下一行 board[row][col] = \'.\'; // 回溯 } } }public: vector<vector> solveNQueens(int n) { vector board(n, string(n, \'.\')); // 初始化空棋盘 backtrack(board, 0); return res; }};

Java

class Solution { private List<List<String>> res = new ArrayList<>(); public List<List<String>> solveNQueens(int n) { char[][] board = new char[n][n]; for (char[] row : board) { Arrays.fill(row, \'.\'); } backtrack(board, 0); return res; } private void backtrack(char[][] board, int row) { if (row == board.length) { res.add(toList(board)); return; } for (int col = 0; col < board.length; col++) { if (isValid(board, row, col)) { board[row][col] = \'Q\'; backtrack(board, row + 1); board[row][col] = \'.\'; } } } private boolean isValid(char[][] board, int row, int col) { // 检查列 for (int i = 0; i < row; i++) { if (board[i][col] == \'Q\') { return false; } } // 检查左上对角线 for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { if (board[i][j] == \'Q\') { return false; } } // 检查右上对角线 for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) { if (board[i][j] == \'Q\') { return false; } } return true; } private List<String> toList(char[][] board) { List<String> list = new ArrayList<>(); for (char[] row : board) { list.add(new String(row)); } return list; }}

Python

class Solution: def solveNQueens(self, n: int) -> List[List[str]]: def backtrack(row): if row == n: res.append([\'\'.join(row) for row in board]) return for col in range(n): if isValid(row, col):  board[row][col] = \'Q\'  backtrack(row + 1)  board[row][col] = \'.\' def isValid(row, col): # 检查列 for i in range(row): if board[i][col] == \'Q\':  return False # 检查左上对角线 i, j = row-1, col-1 while i >=0 and j >=0: if board[i][j] == \'Q\':  return False i, j = i-1, j-1 # 检查右上对角线 i, j = row-1, col+1 while i >=0 and j < n: if board[i][j] == \'Q\':  return False i, j = i-1, j+1 return True res = [] board = [[\'.\' for _ in range(n)] for _ in range(n)] backtrack(0) return res

4、复杂度分析

方法一：数组标记法（高效）

时间复杂度：O(n!)，虽然有剪枝，但最坏情况下仍需遍历所有可能
空间复杂度：O(n)，用于存储检查数组和当前路径

方法二：位置验证法（直观）

时间复杂度：O(n! * n)，每次验证需要O(n)时间
空间复杂度：O(n)，存储当前解的空间

11、二分查找

Q63、搜索插入位置

1、题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:
输入: nums = [1,3,5,6], target = 5输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7输出: 4
提示:

1 <= nums.length <= 104

-104 <= nums[i] <= 104

nums 为 无重复元素 的升序排列数组

-104 <= target <= 104

2、解题思路

二分查找法

初始化：设置左右指针分别指向数组首尾
边界检查：如果目标值大于数组最大值，直接返回数组长度
循环查找 ：
- 计算中间位置
- 比较中间值与目标值
- 调整左右指针
终止条件：当左指针等于右指针时返回位置

3、代码实现

C++

class Solution {public: int searchInsert(vector& nums, int target) { int left = 0; int right = nums.size() - 1; // 特殊处理: 目标值大于数组中所有元素 if (nums[right] < target) { return right + 1; } // 标准二分查找 while (left < right) { int mid = left + (right - left) / 2; // 防止溢出 if (nums[mid] < target) { left = mid + 1; // 目标在右半区 } else { right = mid; // 目标在左半区或者 mid 位置 } } return left; // 最终 left 就是应插入的位置 }};

Java

class Solution { public int searchInsert(int[] nums, int target) { int left = 0; int right = nums.length - 1; // 处理目标值大于数组最大值的情况 if (nums[right] < target) { return right + 1; } // 二分查找 while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else { right = mid; } } return left; }}

Python

class Solution: def searchInsert(self, nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1 # 处理目标值大于数组最大值的情况 if nums[right] < target: return right + 1 # 二分查找 while left < right: mid = left + (right - left) // 2 if nums[mid] < target: left = mid + 1 else: right = mid return left

4、复杂度分析

时间复杂度：O(log n)，标准的二分查找复杂度
空间复杂度：O(1)，只使用了常数级别的额外空间

Q64、搜索二维矩阵

1、题目描述

给你一个满足下述两条属性的 m x n 整数矩阵：

每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13输出：false
提示：

m == matrix.length

n == matrix[i].length

1 <= m, n <= 100

-104 <= matrix[i][j], target <= 104

2、解题思路

两种主要方法

整体二分查找：
- 将二维矩阵视为一个一维数组
- 使用标准的二分查找算法
边界检查+二分查找：
- 先检查目标值是否在矩阵范围内
- 再进行二分查找

3、代码实现

C++

class Solution {public: bool searchMatrix(vector<vector>& matrix, int target) { int m = matrix.size(); // 行数 int n = matrix[0].size(); // 列数 int left = 0; int right = m * n - 1; // 将矩阵视为一维数组的最后一个索引 while (left <= right) { int mid = left + (right - left) / 2; // 防止溢出 int val = matrix[mid / n][mid % n]; // 计算中间值 if (val  target) { right = mid - 1; // 目标在左半区 } else { return true; // 找到目标 } } return false; // 未找到目标 }};

class Solution {public: bool searchMatrix(vector<vector>& matrix, int target) { int m = matrix.size(); int n = matrix[0].size(); // 边界检查: 目标不在矩阵范围内 if (matrix[0][0] > target || matrix[m - 1][n - 1] < target) { return false; } int left = 0; int right = m * n - 1; while (left < right) { int mid = left + (right - left) / 2; int val = matrix[mid / n][mid % n]; if (val < target) { left = mid + 1; // 目标在右半区 } else { right = mid; // 目标在左半区或 mid 位置 } } return matrix[left / n][left % n] == target; }};

Java

class Solution { public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length; int n = matrix[0].length; int left = 0, right = m * n - 1; while (left <= right) { int mid = left + (right - left) / 2; int val = matrix[mid / n][mid % n]; if (val == target) { return true; } else if (val < target) { left = mid + 1; } else { right = mid - 1; } } return false; }}

Python

class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: m, n = len(matrix), len(matrix[0]) left, right = 0, m * n - 1 while left <= right: mid = left + (right - left) // 2 row, col = divmod(mid, n) val = matrix[row][col] if val == target: return True elif val < target: left = mid + 1 else: right = mid - 1 return False

4、复杂度分析

方法一：整体二分查找

时间复杂度：O(log(mn))，标准的二分查找复杂度
空间复杂度：O(1)，使用常数空间

方法二：边界检查+二分查找

时间复杂度：O(log(mn))，边界检查O(1)，二分查找O(log(mn))
空间复杂度：O(1)，使用常数空间

Q65、在排序数组中查找元素的第一个和最后一个位置

1、题目描述

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：
输入：nums = [5,7,7,8,8,10], target = 8输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6输出：[-1,-1]
示例 3：
输入：nums = [], target = 0输出：[-1,-1]
提示：

0 <= nums.length <= 105

-109 <= nums[i] <= 109

nums 是一个非递减数组

-109 <= target <= 109

2、解题思路

二分查找法

查找左边界：
- 使用标准二分查找，但遇到等于目标值时仍向左移动
- 最终 left 指向第一个等于目标值的位置
查找右边界：
- 修改二分查找，遇到等于目标值时向右移动
- 最终 left 指向最后一个等于目标值的位置
边界检查：
- 在查找左边界后检查是否存在目标值
- 如果不存在直接返回 [-1, -1]

3、代码实现

C++

class Solution {public: vector searchRange(vector& nums, int target) { if (nums.empty()) { return {-1, -1}; // 空数组直接返回 } // 查找左边界 int left = 0, right = nums.size() - 1; while (left < right) { int mid = left + (right - left) / 2; // 防止溢出 if (nums[mid] < target) { left = mid + 1; // 目标在右半区 } else { right = mid; // 目标在左半区或 mid 位置 } } int start = left; // 左边界候选 if (nums[start] != target) { return {-1, -1}; // 检查是否存在 } // 查找右边界 right = nums.size() - 1; // 重置右指针 while (left  target) { right = mid - 1; // 目标在左半区 } else { left = mid; // 目标在右半区或者 mid 位置 } } int end = right; return {start, end}; }};

Java

class Solution { public int[] searchRange(int[] nums, int target) { if (nums.length == 0) { return new int[] { -1, -1 }; } // 查找左边界 int left = 0, right = nums.length - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else { right = mid; } } int start = left; if (nums[start] != target) { return new int[] { -1, -1 }; } // 查找右边界 right = nums.length - 1; while (left < right) { int mid = left + (right - left + 1) / 2; if (nums[mid] > target) { right = mid - 1; } else { left = mid; } } int end = right; return new int[] { start, end }; }}

Python

class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: if not nums: return [-1, -1] # 查找左边界 left, right = 0, len(nums) - 1 while left < right: mid = (left + right) // 2 if nums[mid] < target: left = mid + 1 else: right = mid start = left if nums[start] != target: return [-1, -1] # 查找右边界 right = len(nums) - 1 while left < right: mid = (left + right + 1) // 2 # 向上取整 if nums[mid] > target: right = mid - 1 else: left = mid end = right return [start, end]

4、复杂度分析

时间复杂度：O(log n)，两次二分查找
空间复杂度：O(1)，只使用了常数空间

Q66、搜索旋转排序数组

1、题目描述

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3输出：-1
示例 3：
输入：nums = [1], target = 0输出：-1
提示：

1 <= nums.length <= 5000

-104 <= nums[i] <= 104

nums 中的每个值都 独一无二

题目数据保证 nums 在预先未知的某个下标上进行了旋转

-104 <= target <= 104

2、解题思路

二分查找法

基本情况处理：处理空数组和单元素数组的情况
二分查找 ：
- 比较中间元素与目标值
- 判断左半部分或右半部分是否有序
- 根据有序部分确定搜索方向
边界调整：根据比较结果调整左右指针

3、代码实现

C++

class Solution {public: int search(vector& nums, int target) { int n = nums.size(); if (n == 0) { return -1; // 处理空数组情况 } if (n == 1) { return nums[0] == target ? 0 : -1; } int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; // 防止溢出 // 找到目标值 if (nums[mid] == target) { return mid; } // 判断左半部分是否有序 if (nums[left] <= nums[mid]) { // 目标值在有序的左半部分 if (nums[left] <= target && target < nums[mid]) {  right = mid - 1; // 在左半部分继续搜索 } else {  left = mid + 1; // 在右半部分继续搜索 } } // 右半部分有序 else { // 目标值在有序的右半部分 if (nums[mid] < target && target <= nums[right]) {  left = mid + 1; // 在右半部分继续搜索 } else {  right = mid - 1; // 在左半部分继续搜索 } } } return -1; // 未找到目标值 }};

Java

class Solution { public int search(int[] nums, int target) { int n = nums.length; if (n == 0) { return -1; } if (n == 1) { return nums[0] == target ? 0 : -1; } int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } if (nums[left] <= nums[mid]) { if (nums[left] <= target && target < nums[mid]) {  right = mid - 1; } else {  left = mid + 1; } } else { if (nums[mid] < target && target <= nums[right]) {  left = mid + 1; } else {  right = mid - 1; } } } return -1; }}

Python

class Solution: def search(self, nums: List[int], target: int) -> int: n = len(nums) if n == 0: return -1 if n == 1: return 0 if nums[0] == target else -1 left, right = 0, n - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid # 左半部分有序 if nums[left] <= nums[mid]: if nums[left] <= target < nums[mid]:  right = mid - 1 else:  left = mid + 1 # 右半部分有序 else: if nums[mid] < target <= nums[right]:  left = mid + 1 else:  right = mid - 1 return -1

4、复杂度分析

时间复杂度：O(log n)，标准的二分查找复杂度
空间复杂度：O(1)，只使用了常数空间

《LeetCode 热题 100》整整 100 题量大管饱题解套餐 中

Q34、合并 K 个升序链表

1、题目描述

2、解题思路

3、代码实现

C++

Java

Python

4、复杂度分析

Q35、LRU 缓存

1、题目描述

2、解题思路

3、代码实现

C++

Java

Python

4、复杂度分析

8、二叉树

Q36、二叉树的中序遍历

1、题目描述

2、解题思路

3、代码实现

C++

Java

Python

4、复杂度分析

Q37、二叉树的最大深度

1、题目描述

2、解题思路

3、代码实现

C++

Java

Python

4、复杂度分析

Q38、翻转二叉树

1、题目描述

2、解题思路

3、代码实现

C++

Java

Python

4、复杂度分析

Q39、对称二叉树

1、题目描述

2、解题思路

3、代码实现

C++

Java

Python

4、复杂度分析

Q40、二叉树的直径

1、题目描述

2、解题思路

3、代码实现

C++

Java

Python

4、复杂度分析

Q41、二叉树的层序遍历

1、题目描述

2、解题思路

3、代码实现

C++

Java

Python

4、复杂度分析

Q42、将有序数组转换为二叉搜索树

1、题目描述

2、解题思路

3、代码实现

C++

Java

Python

4、复杂度分析

Q43、验证二叉搜索树

1、题目描述

2、解题思路

3、代码实现

C++

Java

《LeetCode 热题 100》整整 100 题量大管饱题解套餐中