Hard
题目描述
给你一棵有 n 个节点的无向树，节点编号从 0 到 n - 1。这棵树用长度为 n - 1 的二维整数数组 edges 表示，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条边。
同时给你两个长度为 n 的二进制字符串 start 和 target。对于每个节点 x，start[x] 是它的初始颜色，target[x] 是它的目标颜色。
在一次操作中，你可以选择索引为 i 的边并翻转其两个端点。也就是说，如果边是 [u, v]，那么节点 u 和 v 的颜色都会从 ‘0’ 翻转为 ‘1’ 或从 ‘1’ 翻转为 ‘0’。
返回一个边索引数组，其操作能将 start 转换为 target。在所有最小长度的有效序列中，返回边索引按递增顺序排列的序列。
如果无法将 start 转换为 target，返回包含单个元素 -1 的数组。
示例 1：
输入：n = 3, edges = [[0,1],[1,2]], start = "010", target = "100"
输出：[0]
解释：
翻转索引为 0 的边，这会翻转节点 0 和 1。
字符串从 "010" 变为 "100"，匹配目标。
示例 2：
输入：n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[3,5],[1,6]], start = "0011000", target = "0010001"
输出：[1,2,5]
解释：
翻转索引为 1 的边，这会翻转节点 1 和 2。
翻转索引为 2 的边，这会翻转节点 2 和 3。
翻转索引为 5 的边，这会翻转节点 1 和 6。
这些操作后，结果字符串变为 "0010001"，匹配目标。
示例 3：
输入：n = 2, edges = [[0,1]], start = "00", target = "01"
输出：[-1]
解释：
没有边翻转序列能将 "00" 转换为 "01"。因此，我们返回 [-1]。
约束条件：
2 <= n == start.length == target.length <= 10^5edges.length == n - 1edges[i] = [ai, bi]0 <= ai, bi < nstart[i]是 ‘0’ 或 ‘1’target[i]是 ‘0’ 或 ‘1’- 输入保证
edges表示一棵有效的树
解题思路
这道题是一个关于树上节点状态翻转的优化问题。核心思路是使用深度优先搜索（DFS）自底向上地处理每个节点。
基本思路：
- 根节点选择：可以选择任意节点作为根节点，这里选择节点 0。
- DFS遍历：从根节点开始深度优先搜索，先处理子树，再处理当前节点。
- 状态传播：维护每个节点当前的实际状态（考虑祖先节点的翻转操作影响）。
- 贪心决策：对于每个节点，如果其当前状态与目标状态不匹配，则必须翻转连接它与父节点的边。
关键观察：
- 翻转一条边会同时影响边的两个端点
- 从叶子节点向根节点处理时，每个节点的状态只能通过翻转它与父节点之间的边来改变
- 这种贪心策略是最优的，因为每条边最多需要翻转一次
算法步骤：
- 构建树的邻接表表示
- 使用DFS遍历，维护每个节点受祖先翻转影响后的实际状态
- 对于每个节点，如果实际状态与目标状态不符，记录需要翻转的边
- 返回所有需要翻转的边索引（已按递增顺序）
可行性检查： 在树的结构下，任何合法的状态转换都是可能的，因为我们总能通过适当的边翻转达到目标状态。只有当问题本身存在矛盾时才会返回-1。
代码实现
class Solution {
public:
vector<int> minimumFlips(int n, vector<vector<int>>& edges, string start, string target) {
vector<vector<pair<int, int>>> adj(n);
// 构建邻接表，存储邻居节点和边的索引
for (int i = 0; i < edges.size(); i++) {
int u = edges[i][0], v = edges[i][1];
adj[u].push_back({v, i});
adj[v].push_back({u, i});
}
vector<int> result;
function<void(int, int, int)> dfs = [&](int node, int parent, int flips) {
// 计算当前节点的实际状态
int current = (start[node] - '0') ^ (flips & 1);
int target_val = target[node] - '0';
// 先处理所有子节点
for (auto& [child, edge_idx] : adj[node]) {
if (child != parent) {
dfs(child, node, flips);
}
}
// 重新计算当前状态（因为子节点可能进行了翻转）
current = (start[node] - '0') ^ (flips & 1);
// 如果当前状态与目标不符，需要翻转与父节点的边
if (current != target_val && parent != -1) {
// 找到连接当前节点和父节点的边
for (auto& [neighbor, edge_idx] : adj[node]) {
if (neighbor == parent) {
result.push_back(edge_idx);
// 更新翻转计数
flips++;
break;
}
}
}
};
dfs(0, -1, 0);
// 检查根节点是否满足目标
int root_flips = 0;
for (int edge_idx : result) {
if (edges[edge_idx][0] == 0 || edges[edge_idx][1] == 0) {
root_flips++;
}
}
int root_state = (start[0] - '0') ^ (root_flips & 1);
if (root_state != (target[0] - '0')) {
return {-1};
}
sort(result.begin(), result.end());
return result;
}
};
class Solution:
def minimumFlips(self, n: int, edges: List[List[int]], start: str, target: str) -> List[int]:
from collections import defaultdict
# 构建邻接表
adj = defaultdict(list)
for i, (u, v) in enumerate(edges):
adj[u].append((v, i))
adj[v].append((u, i))
result = []
def dfs(node, parent, flips):
# 先处理所有子节点
for child, edge_idx in adj[node]:
if child != parent:
dfs(child, node, flips)
# 计算当前节点的实际状态
current = int(start[node]) ^ (flips & 1)
target_val = int(target[node])
# 如果当前状态与目标不符且不是根节点，需要翻转与父节点的边
if current != target_val and parent != -1:
for neighbor, edge_idx in adj[node]:
if neighbor == parent:
result.append(edge_idx)
flips += 1
break
dfs(0, -1, 0)
# 检查根节点是否满足目标
root_flips = sum(1 for edge_idx in result if 0 in edges[edge_idx])
root_state = int(start[0]) ^ (root_flips & 1)
if root_state != int(target[0]):
return [-1]
return sorted(result)
public class Solution {
public IList<int> MinimumFlips(int n, int[][] edges, string start, string target) {
var adj = new List<List<(int, int)>>(n);
for (int i = 0; i < n; i++) {
adj.Add(new List<(int, int)>());
}
// 构建邻接表
for (int i = 0; i < edges.Length; i++) {
int u = edges[i][0], v = edges[i][1];
adj[u].Add((v, i));
adj[v].Add((u, i));
}
var result = new List<int>();
void Dfs(int node, int parent, int flips) {
// 先处理所有子节点
foreach (var (child, edgeIdx) in adj[node]) {
if (child != parent) {
Dfs(child, node, flips);
}
}
// 计算当前节点的实际状态
int current = (start[node] - '0') ^ (flips & 1);
int targetVal = target[node] - '0';
// 如果当前状态与目标不符且不是根节点，需要翻转与父节点的边
if (current != targetVal && parent != -1) {
foreach (var (neighbor, edgeIdx) in adj[node]) {
if (neighbor == parent) {
result.Add(edgeIdx);
flips++;
break;
}
}
}
}
Dfs(0, -1, 0);
// 检查根节点是否满足目标
int rootFlips = 0;
foreach (int edgeIdx in result) {
if (edges[edgeIdx][0] == 0 || edges[edgeIdx][1] == 0) {
rootFlips++;
}
}
int rootState = (start[0] - '0') ^ (rootFlips & 1);
if (rootState != (target[0] - '0')) {
return new List<int> { -1 };
}
result.Sort();
return result;
}
}
var minimumFlips = function(n, edges, start, target) {
const graph = Array.from({ length: n }, () => []);
for (let i = 0; i < edges.length; i++) {
const [u, v] = edges[i];
graph[u].push([v, i]);
graph[v].push([u, i]);
}
const diff = Array(n);
for (let i = 0; i < n; i++) {
diff[i] = start[i] !== target[i] ? 1 : 0;
}
const result = [];
const visited = new Set();
function dfs(node, parent) {
visited.add(node);
for (const [neighbor, edgeIdx] of graph[node]) {
if (neighbor === parent) continue;
if (!visited.has(neighbor)) {
dfs(neighbor, node);
if (diff[neighbor] === 1) {
result.push(edgeIdx);
diff[node] ^= 1;
diff[neighbor] ^= 1;
}
}
}
}
dfs(0, -1);
for (let i = 0; i < n; i++) {
if (diff[i] === 1) {
return [-1];
}
}
result.sort((a, b) => a - b);
return result;
};
复杂度分析
| 复杂度 | 分析 |
|---|---|
| 时间复杂度 | O(n) |
| 空间复杂度 | O(n) |
时间复杂度分析：DFS遍历每个节点一次，每个节点的处理时间为O(度数)，总时间复杂度为O(n)。 空间复杂度分析：邻接表存储需要O(n)空间，递归调用栈深度最大为O(n)，总空间复杂度为O(n)。