当前位置：首页 > news >正文

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

news 2025/7/29 6:46:32

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<ListNode*>& 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 < l2->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<ListNode*>& lists) {return merge(lists, 0, lists.size() - 1);}private:ListNode* merge(vector<ListNode*>& 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 < l2->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<ListNode*>& lists) {priority_queue<ListNode*, vector<ListNode*>, 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 = dummywhile heap:val, idx, node = heapq.heappop(heap)cur.next = nodecur = cur.nextif 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);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

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

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<int, DLinkedNode*> 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 = keyself.value = valueself.prev = Noneself.next = Noneclass LRUCache:def __init__(self, capacity: int):self.cache = dict()self.capacity = capacityself.size = 0# 使用伪头部和伪尾部节点self.head = DLinkedNode()self.tail = DLinkedNode()self.head.next = self.tailself.tail.prev = self.headdef get(self, key: int) -> int:if key not in self.cache:return -1# 如果key存在，先通过哈希表定位，再移到头部node = self.cache[key]self.moveToHead(node)return node.valuedef 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 += 1if self.size > self.capacity:# 如果超出容量，删除双向链表的尾部节点removed = self.removeTail()# 删除哈希表中对应的项self.cache.pop(removed.key)self.size -= 1else:# 如果key存在，先通过哈希表定位，再修改value，并移到头部node = self.cache[key]node.value = valueself.moveToHead(node)def addToHead(self, node: DLinkedNode) -> None:node.prev = self.headnode.next = self.head.nextself.head.next.prev = nodeself.head.next = nodedef removeNode(self, node: DLinkedNode) -> None:node.prev.next = node.nextnode.next.prev = node.prevdef moveToHead(self, node: DLinkedNode) -> None:self.removeNode(node)self.addToHead(node)def removeTail(self) -> DLinkedNode:node = self.tail.prevself.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<int> inorderTraversal(TreeNode* root) {vector<int> result;inorder(root, result);return result;}private:void inorder(TreeNode* node, vector<int>& res) {if (node == nullptr) {return;}inorder(node->left, res);  // 遍历左子树res.push_back(node->val);  // 访问当前节点inorder(node->right, res); // 遍历右子树}
};

// 方法2: 迭代法
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> 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 resdef inorder(self, node, res):if not node:returnself.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 = rootwhile curr or stack:# 将当前节点及其所有左子节点入栈while curr:stack.append(curr)curr = curr.left# 访问栈顶节点curr = stack.pop()res.append(curr.val)# 转向处理右子树curr = curr.rightreturn 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<TreeNode*> q;q.push(root);int depth = 0;while (!q.empty()) {int levelSize = q.size(); // 当前层节点数depth++;                  // 深度+1// 遍历当前层所有节点for (int i = 0; i < levelSize; ++i) {TreeNode* node = q.front();q.pop();// 将下一层节点加入队列if (node->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 0left_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 0queue = deque([root])depth = 0while 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<TreeNode*> 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 Nonequeue = 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<TreeNode*> 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 Truereturn 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 Truequeue = 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 = 0def depth(node):if not node:return 0left_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) + 1depth(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<int>> levelOrder(TreeNode* root) {vector<vector<int>> result; // 存储最终结果if (root == nullptr) {return result;}queue<TreeNode*> q; // 辅助列表q.push(root);while (!q.empty()) {int level_size = q.size(); // 当前层的节点数vector<int> current_level; // 存储当前层的节点值// 处理当前层所有节点for (int i = 0; i < level_size; ++i) {TreeNode* node = q.front();q.pop();current_level.push_back(node->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 resultqueue = 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)，最坏情况下队列存储所有叶子节点

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 <= prev) {return false;}prev = root->val; // 更新前驱// 检查右子树return isValidBST(root->right);}
};

// 方法2: 迭代中序遍历
class Solution {
public:bool isValidBST(TreeNode* root) {stack<TreeNode*> 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 <= prev) {return false;}prev = root->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 Trueif not helper(node.left):return Falseif node.val <= self.prev:return Falseself.prev = node.valreturn 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.leftroot = stack.pop()if root.val <= prev:return Falseprev = root.valroot = root.rightreturn 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<TreeNode*> 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 = kself.result = 0self.inorder(root)return self.resultdef inorder(self, node):if not node or self.k == 0:returnself.inorder(node.left) # 遍历左子树self.k -= 1if self.k == 0: # 处理当前节点self.result = node.valreturnself.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.leftroot = stack.pop()k -= 1if k == 0: # 找到第k小的元素return root.valroot = 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<int> rightSideView(TreeNode* root) {vector<int> result;if (!root) {return result;}queue<TreeNode*> q;q.push(root);while (!q.empty()) {int size = q.size();for (int i = 0; i < size; ++i) {TreeNode* node = q.front();q.pop();// 记录每层最后一个节点if (i == size - 1) {result.push_back(node->val);}if (node->left) {q.push(node->left);}if (node->right) {q.push(node->right);}}}return result;}
};

// 方法2: DFS (递归)
class Solution {
public:vector<int> rightSideView(TreeNode* root) {vector<int> result;dfs(root, 0, result);return result;}private:void dfs(TreeNode* node, int depth, vector<int>& 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<int> rightSideView(TreeNode* root) {vector<int> result;if (!root) {return result;}stack<pair<TreeNode*, int>> 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: BFS
class 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: DFS
class 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

# BFS
class 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

# DFS
class Solution:def rightSideView(self, root: Optional[TreeNode]) -> List[int]:result = []def dfs(node, depth):if not node:returnif 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<TreeNode*> nodes;preorder(root, nodes);for (int i = 1; i < nodes.size(); ++i) {nodes[i - 1]->left = nullptr;nodes[i - 1]->right = nodes[i];}}private:void preorder(TreeNode* node, vector<TreeNode*>& 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<TreeNode*> 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 = rootwhile curr:if curr.left:predecessor = curr.leftwhile predecessor.right:predecessor = predecessor.rightpredecessor.right = curr.rightcurr.right = curr.leftcurr.left = Nonecurr = 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<int>& preorder, vector<int>& 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<int, int> indexMap;TreeNode* build(vector<int>& 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<int>& preorder, vector<int>& 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<int> leftPre(preorder.begin() + 1, preorder.begin() + 1 + pos);vector<int> leftIn(inorder.begin(), inorder.begin() + pos);// 构建右子树的前序和中序数组vector<int> rightPre(preorder.begin() + 1 + pos, preorder.end());vector<int> 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<int>& preorder, vector<int>& inorder) {if (preorder.empty()) {return nullptr;}stack<TreeNode*> s;TreeNode* root = new TreeNode(preorder[0]);s.push(root);int inorderIndex = 0;for (int i = 1; i < preorder.size(); ++i) {TreeNode* node = s.top();if (node->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 Noneroot_val = preorder[pre_start]root = TreeNode(root_val)in_root = index_map[root_val]left_size = in_root - in_startroot.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 rootreturn 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<long, int> prefix; // 存储前缀和及其出现次数prefix[0] = 1;                   // 初始化: 前缀和为 0 出现 1 次return dfs(root, 0, targetSum, prefix);}private:int dfs(TreeNode* root, long currSum, int target, unordered_map<long, int>& 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 defaultdictdef dfs(node, curr_sum):if not node:return 0nonlocal countcurr_sum += node.valcount += prefix[curr_sum - targetSum]prefix[curr_sum] += 1dfs(node.left, curr_sum)dfs(node.right, curr_sum)prefix[curr_sum] -= 1prefix = defaultdict(int)prefix[0] = 1  # 初始前缀和为0出现1次count = 0dfs(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 和 qTreeNode* left = lowestCommonAncestor(root->left, p, q);TreeNode* right = lowestCommonAncestor(root->right, p, q);// 如果 p 和 q 分别位于左右子树, 当前节点就是 LCAif (left && right) {return root;}// 否则返回非空的那个子树结果return left ? left : right;}
};

// 方法2: 哈希表记录父亲节点
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {unordered_map<TreeNode*, TreeNode*> parent; // 父节点映射unordered_set<TreeNode*> visited;           // 访问标记// DFS 遍历树, 记录每个节点的父亲节点stack<TreeNode*> 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 rootleft = self.lowestCommonAncestor(root.left, p, q)right = self.lowestCommonAncestor(root.right, p, q)if left and right:return rootreturn left if left else right

4、复杂度分析

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

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

1、题目描述

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

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

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

示例 1：

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

示例 2：

输入：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 0left_gain = max(max_gain(node.left), 0)right_gain = max(max_gain(node.right), 0)new_path_sum = node.val + left_gain + right_gainself.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: DFS
class Solution {
private:const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};void dfs(vector<vector<char>>& grid, vector<vector<bool>>& 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 < grid.size() && y >= 0 && y < grid[0].size() &&grid[x][y] == '1' && !visited[x][y]) {dfs(grid, visited, x, y);}}}public:int numIslands(vector<vector<char>>& grid) {if (grid.empty() || grid[0].empty()) {return 0;}int m = grid.size(), n = grid[0].size();vector<vector<bool>> visited(m, vector<bool>(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: BFS
class Solution {
public:int numIslands(vector<vector<char>>& 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<int, int>> 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 < m && ny >= 0 && ny < n && grid[nx][ny] == '1') {grid[nx][ny] = '0';q.push({nx, ny});}}}}}}return count;}
};

Java

// 方法2: BFS
class 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: BFS
class Solution:def numIslands(self, grid: List[List[str]]) -> int:if not grid:return 0m, n = len(grid), len(grid[0])count = 0def dfs(i, j):if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':returngrid[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 += 1dfs(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<int>>& grid) {if (grid.empty() || grid[0].empty()) {return 0;}int m = grid.size(), n = grid[0].size();queue<pair<int, int>> 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;}}}// 如果没有新鲜橘子, 直接返回 0if (fresh == 0) {return 0;}int minutes = 0;while (!q.empty()) {int size = q.size();bool infected = false; // 标记本轮是否有句子被感染for (int i = 0; i < size; ++i) {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 < m && ny >= 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 0m, n = len(grid), len(grid[0])queue = deque()fresh = 0for i in range(m):for j in range(n):if grid[i][j] == 2:queue.append((i, j))elif grid[i][j] == 1:fresh += 1if fresh == 0:return 0minutes = 0dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]while queue:size = len(queue)infected = Falsefor _ in range(size):x, y = queue.popleft()for dx, dy in dirs:nx, ny = x + dx, y + dyif 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:grid[nx][ny] = 2queue.append((nx, ny))fresh -= 1infected = Trueif infected:minutes += 1return 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: DFS
class Solution {
private:vector<vector<int>> edges; // 邻接表vector<int> visited;       // 访问状态: 0 未访问, 1 访问中, 2 已访问bool valid = true;         // 是否有效 (无环)void dfs(int u) {visited[u] = 1; // 标记为访问中for (int v : edges[u]) {// 遇到未访问节点, 继续 DFSif (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<int>>& prerequisites) {edges.resize(numCourses);visited.resize(numCourses);// 构建邻接表for (const auto& p : prerequisites) {edges[p[1]].push_back(p[0]);}// 对每个未访问节点进行 DFSfor (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<int>>& prerequisites) {vector<vector<int>> edges(numCourses); // 邻接表vector<int> indeg(numCourses);         // 入度表// 构建邻接表和入度表for (const auto& p : prerequisites) {edges[p[1]].push_back(p[0]);indeg[p[0]]++;}queue<int> 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] * numCoursesfor p in prerequisites:edges[p[1]].append(p[0])indeg[p[0]] += 1q = deque([i for i in range(numCourses) if indeg[i] == 0])visited = 0while q:u = q.popleft()visited += 1for v in edges[u]:indeg[v] -= 1if indeg[v] == 0:q.append(v)return visited == numCourses

4、复杂度分析

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

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

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<int>> ret; // 存储所有排列结果vector<int> path;        // 当前路径bool check[7];           // 标记数组, 记录数字是否已经使用void dfs(vector<int>& 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<int>> permute(vector<int>& 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[:])  # 添加当前排列的副本returnfor i in range(len(nums)):if not used[i]:path.append(nums[i])used[i] = Truebacktrack(path, used)# 回溯path.pop()used[i] = Falseres = []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<int>> ret; // 存储所有子集结果vector<int> path;        // 当前路径void dfs(vector<int>& 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<int>> subsets(vector<int>& nums) {dfs(nums, 0);return ret;}
};

// 方法2: 迭代回溯
class Solution {
private:vector<vector<int>> ret;vector<int> path;void dfs(vector<int>& 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<int>> subsets(vector<int>& 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<Integer>> res = new ArrayList<>();private List<Integer> 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<Integer>> 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 不对应任何字母。

示例 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<string> 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<string> 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))returnfor 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<int>> ret;vector<int> path;void dfs(vector<int>& 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<int>> combinationSum(vector<int>& candidates, int target) {dfs(candidates, 0, target);return ret;}
};

// 方法2: 带当前和的回溯
class Solution {
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<vector<int>> solutions;vector<int> solution;dfs(solutions, solution, 0, 0, target, candidates);return solutions;}void dfs(vector<vector<int>>& solutions, vector<int>& solution, int curSum, int preIdx, int target, vector<int>& 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+1dfs(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())returnif target < 0:returnfor 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<string> generateParenthesis(int n) {vector<string> ret;      // 存储所有有效组合string path;             // 当前路径dfs(ret, path, 0, 0, n); // 初始左右括号都为 0return ret;}void dfs(vector<string>& ret, string& path, int left, int right, int n) {// 当右括号达到 n 对, 记录有效组合if (right == n) {ret.push_back(path);return;}// 可以添加左括号条件: 左括号数小于 nif (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))returnif 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<char>>& board, string& word, vector<vector<bool>>& visited, int i, int j, int pos) {// 匹配完成if (pos == word.size()) {return true;}for (int k = 0; k < 4; ++k) {int x = i + dir[k][0];int y = j + dir[k][1];// 检查边界、是否访问过、是否匹配当前字符if (x >= 0 && x < board.size() && y >= 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<char>>& board, string word) {int m = board.size(), n = board[0].size();vector<vector<bool>> visited(m, vector<bool>(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 Truefor dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:x, y = i + dx, j + dyif 0 <= x < m and 0 <= y < n and not visited[x][y] and board[x][y] == word[pos]:visited[x][y] = Trueif dfs(x, y, pos + 1):return Truevisited[x][y] = Falsereturn Falsem, 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] = Trueif dfs(i, j, 1):return Truevisited[i][j] = Falsereturn 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<bool>> dp;    // dp[i][j] 表示 s[i...j] 是否是回文vector<vector<string>> ret; // 存储所有结果vector<string> 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<string>> partition(string s) {n = s.size();dp.assign(n, vector<bool>(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<bool>> dp;    // 记忆化数组vector<vector<string>> ret; // 存储所有结果vector<string> 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 (isPalindrome(s, i, j)) {ans.push_back(s.substr(i, j - i + 1)); // 加入当前方案dfs(s, j + 1);                         // 继续处理剩余部分ans.pop_back();                        // 回溯}}}// 判断 s[i...j] 是否是回文(带记忆化)bool isPalindrome(const string& s, int i, int j) {if (dp[i][j]) {return dp[i][j]; // 已经计算过了}if (i >= j) {return dp[i][j] = true; // 单个字符或空串}return dp[i][j] = (s[i] == s[j]) ? isPalindrome(s, i + 1, j - 1) : false;}public:vector<vector<string>> partition(string s) {n = s.size();dp.assign(n, vector<bool>(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] = Trueelif 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())returnfor 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：

输入：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<string>> res; // 存储所有结果vector<string> 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<string>> solveNQueens(int n) {this->n = n;board.resize(n, string(n, '.')); // 初始化空棋盘backtrack(0);return res;}
};

// 方法2: 位置验证法
class Solution {
private:vector<vector<string>> res; // 存储所有结果// 验证当前位置是否合法bool isValid(vector<string>& board, int row, int col) {int n = board.size();// 检查列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 < n; --i, ++j) {if (board[i][j] == 'Q') {return false;}}return true;}void backtrack(vector<string>& 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<string>> solveNQueens(int n) {vector<string> 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])returnfor 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-1while i >=0 and j >=0:if board[i][j] == 'Q':return Falsei, j = i-1, j-1# 检查右上对角线i, j = row-1, col+1while i >=0 and j < n:if board[i][j] == 'Q':return Falsei, j = i-1, j+1return Trueres = []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<int>& 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) // 2if nums[mid] < target:left = mid + 1else:right = midreturn 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<int>>& 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) {left = mid + 1; // 目标在右半区} else if (val > target) {right = mid - 1; // 目标在左半区} else {return true; // 找到目标}}return false; // 未找到目标}
};

class Solution {
public:bool searchMatrix(vector<vector<int>>& 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 - 1while left <= right:mid = left + (right - left) // 2row, col = divmod(mid, n)val = matrix[row][col]if val == target:return Trueelif val < target:left = mid + 1else:right = mid - 1return False

4、复杂度分析

方法一：整体二分查找

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

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

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

在传递给函数之前，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<int>& 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 -1if n == 1:return 0 if nums[0] == target else -1left, right = 0, n - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return mid# 左半部分有序if nums[left] <= nums[mid]:if nums[left] <= target < nums[mid]:right = mid - 1else:left = mid + 1# 右半部分有序else:if nums[mid] < target <= nums[right]:left = mid + 1else:right = mid - 1return -1