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.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[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 = 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); // 返回 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 <= 30000 <= key <= 100000 <= 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 = key
self.value = value
self.prev = None
self.next = None
class 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<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 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<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 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<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 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<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 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<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 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] <= 104nums按 严格递增 顺序排列
2、解题思路
方法：递归分治法
平衡BST性质 ：
- 左子树所有节点值 < 根节点值
- 右子树所有节点值 > 根节点值
- 左右子树高度差不超过1
关键观察 ：
- 有序数组的中间元素适合作为根节点
- 左右子数组可以递归构建左右子树
实现步骤 ：
- 找到数组中间元素作为根节点
- 左子数组构建左子树
- 右子数组构建右子树
3、代码实现
C++
// 方法1: 选择中间左边的元素作为根
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return buildBST(nums, 0, nums.size() - 1);
}
private:
TreeNode* buildBST(vector<int>& 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<int>& nums) {
return buildBST(nums, 0, nums.size() - 1);
}
private:
TreeNode* buildBST(vector<int>& 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 <= 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 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 <= 1040 <= 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 = 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<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:
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<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 = 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 <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder和inorder均 无重复 元素inorder均出现在preorderpreorder保证 为二叉树的前序遍历序列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 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<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 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 != qp和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<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 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：
输入：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 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.lengthn == grid[i].length1 <= m, n <= 300grid[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 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.lengthn == grid[i].length1 <= m, n <= 10grid[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;
}
}
}
// 如果没有新鲜橘子, 直接返回 0
if (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 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 <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCoursesprerequisites[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]) {
// 遇到未访问节点, 继续 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<int>>& 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<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] * 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"); // 返回 True trie.search("app"); // 返回 False trie.startsWith("app"); // 返回 True trie.insert("app"); trie.search("app"); // 返回 True提示：
1 <= word.length, prefix.length <= 2000word和prefix仅由小写英文字母组成insert、search和startsWith调用次数 总计 不超过3 * 104次
2、解题思路
Trie是一种树形数据结构，用于高效存储和检索字符串。每个节点包含：
- 子节点指针数组（26个对应小写字母）
- 结束标志位（标记是否为一个完整单词的结尾）
核心操作
- 插入：沿着字符串字符逐个创建/访问节点
- 搜索：检查是否能完整遍历字符串路径且结尾标记为true
- 前缀搜索：只需检查是否能遍历完前缀路径
3、代码实现
C++
class Trie {
private:
vector<Trie*> 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] <= 10nums中的所有整数 互不相同
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[:]) # 添加当前排列的副本
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<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 <= 4digits[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))
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 <= 302 <= candidates[i] <= 40candidates的所有元素 互不相同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+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<string> generateParenthesis(int n) {
vector<string> ret; // 存储所有有效组合
string path; // 当前路径
dfs(ret, path, 0, 0, n); // 初始左右括号都为 0
return ret;
}
void dfs(vector<string>& 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.lengthn = board[i].length1 <= m, n <= 61 <= word.length <= 15board和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 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 <= 16s仅由小写英文字母组成
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] = 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(n2n)，预处理O(n2)，回溯O(n2n)
- 空间复杂度：O(n2)，存储dp数组
方法二：记忆化搜索+回溯
- 时间复杂度：O(n*2n)
- 空间复杂度：O(n2)
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])
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] <= 104nums为 无重复元素 的 升序 排列数组-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) // 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.lengthn == matrix[i].length1 <= 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 - 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] <= 109nums是一个非递减数组-109 <= target <= 109
2、解题思路
二分查找法
查找左边界：
- 使用标准二分查找，但遇到等于目标值时仍向左移动
- 最终 left 指向第一个等于目标值的位置
查找右边界：
- 修改二分查找，遇到等于目标值时向右移动
- 最终 left 指向最后一个等于目标值的位置
边界检查：
- 在查找左边界后检查是否存在目标值
- 如果不存在直接返回 [-1, -1]
3、代码实现
C++
class Solution {
public:
vector<int> searchRange(vector<int>& 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 < right) {
int mid = left + (right - left + 1) / 2; // 向上取整
if (nums[mid] > 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] <= 104nums中的每个值都 独一无二- 题目数据保证
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 -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)，只使用了常数空间