2026-05-22：翻转树上最少边。用go语言，给你一棵有 n 个节点的无向树，节点编号为 0 到 n-1。树用数组 edges 表示：共有 n-1 条边，edges[i]=[ai, bi] 表示

2026-05-22翻转树上最少边。用go语言给你一棵有 n 个节点的无向树节点编号为 0 到 n-1。树用数组 edges 表示共有 n-1 条边edges[i][ai, bi] 表示 i 号边连接节点 ai 和 bi。再给你两个长度为 n 的二进制字符串 start 和 target其中 start[x] 是节点 x 的初始颜色target[x] 是节点 x 的目标颜色。你可以进行若干次操作。每次操作你会选择一条边的下标 i并把这条边两端点的颜色同时翻转如果两端点原来是 0/1那么翻转后就变成相反的颜色。也就是说选择边 [u, v] 后节点 u 与节点 v 的颜色都会从 0 变 1 或从 1 变 0。你的任务是找出一组边下标序列使得按顺序对这些边执行翻转操作后最终 start 能变成 target。要求在所有可行的边序列中找出“操作次数最少”的序列如果有多种最短方案则把对应的边下标按升序返回。若无论如何都无法把 start 变成 target则返回 [-1]。2 n start.length target.length 100000。edges.length n - 1。edges[i] [ai, bi]。0 ai, bi n。start[i] 是 ‘0’ 或 ‘1’。target[i] 是 ‘0’ 或 ‘1’。输入数据保证 edges 构成一棵有效的树。输入 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”与目标匹配。题目来自力扣3812。解题过程先明确核心规则树是无向的n 个节点n-1 条边边有固定下标每次翻转一条边会同时翻转这条边两个端点的颜色0↔1目标用最少次数的翻转让start颜色变成target颜色最少方案下边下标按升序返回无解返回[-1]。第一步构建树的邻接表存储结构把无向树转换成便于遍历的存储结构给每个节点记录它相邻的节点同时记录这条相邻边的下标因为是无向边每条边会在两个端点的邻接列表里各存一份作用后续可以从根节点出发沿着邻接关系遍历整棵树且能精准找到每条边的下标。第二步确定遍历方式深度优先搜索 DFS选择根节点固定为 0 号节点用后序遍历的方式遍历整棵树从根节点 0 开始递归访问它的所有子节点遍历顺序先处理所有子节点 → 再回到当前节点自底向上处理遍历过程中会区分父节点和子节点避免回头遍历保证树的遍历无环。第三步核心判断逻辑当前节点是否需要翻转遍历到每个节点x时做两个关键判断初始状态对比当前节点x的start颜色和target颜色如果颜色不一致说明当前节点需要翻转如果颜色一致说明当前节点暂时不需要翻转。子节点影响递归处理完所有子节点后如果子节点触发了边翻转会间接改变当前节点的颜色因为边连接父子节点翻边会同时改两端子节点的翻边操作会反转当前节点的需求需要→不需要不需要→需要。第四步标记需要翻转的边遍历过程中一旦确定父子节点之间的边需要翻转直接标记这条边的下标为「需要翻转」翻转这条边会同时改变父节点和子节点的颜色刚好修正子节点的颜色偏差所有标记操作都在遍历中完成只记录需要翻转的边不重复操作保证最少次数。第五步最终合法性校验遍历完整棵树后回到根节点0号节点根节点没有父节点无法通过翻边单独修正它的颜色如果最终根节点的颜色依然和目标不一致说明无解直接返回[-1]如果根节点颜色一致说明所有标记的边就是最少操作方案。第六步整理结果升序输出遍历所有边的标记结果把所有标记为需要翻转的边下标按升序收集起来返回这个有序列表就是最终答案。针对示例输入的完整执行过程对应你的测试用例输入n7边[[0,1],[1,2],[2,3],[3,4],[3,5],[1,6]]start0011000target0010001构建邻接表记录每个节点的邻居和对应边下标从根节点0开始DFS遍历顺序0→1→2→3→4、3→5、1→6自底向上检查每个节点颜色节点4、5颜色匹配无需翻边节点3颜色不匹配触发翻转边2连接2-3节点2被间接翻转后颜色不匹配触发翻转边1连接1-2节点6颜色不匹配触发翻转边5连接1-6所有子节点处理完毕根节点0颜色匹配目标校验通过收集翻转的边下标1、2、5升序输出[1,2,5]。时间复杂度 额外空间复杂度1. 总时间复杂度O(n)树有 n 个节点、n-1 条边邻接表构建遍历所有边O(n)DFS 遍历每个节点仅访问一次每条边仅遍历两次无向边总操作数 O(n)结果收集遍历所有边O(n)整体线性时间与节点数成正比。2. 总额外空间复杂度O(n)邻接表存储存储 n 个节点和 n-1 条边空间 O(n)翻转标记数组长度 n-1空间 O(n)DFS 递归栈树的深度最坏为 O(n)链状树结果数组最坏存储所有 n-1 条边O(n)所有额外空间总和与节点数成正比为线性空间。总结解题核心自底向上DFS遍历通过子节点的翻边操作修正父节点颜色保证最少操作次数无解判断根节点最终颜色无法匹配目标效率时间和空间均为线性复杂度 O(n)完全适配题目 n≤10⁵ 的大数据量要求。Go完整代码如下packagemainimport(fmt)funcminimumFlips(nint,edges[][]int,start,targetstring)(ans[]int){typeedgestruct{to,iint}g:make([][]edge,n)fori,e:rangeedges{x,y:e[0],e[1]g[x]append(g[x],edge{y,i})g[y]append(g[y],edge{x,i})}revs:make([]bool,n-1)// 返回是否需要翻转 x-fa 这条边vardfsfunc(int,int)booldfsfunc(x,faint)bool{rev:start[x]!target[x]// x-fa 是否要翻转for_,e:rangeg[x]{y:e.toify!fadfs(y,x){revs[e.i]true// 需要翻转 y-xrev!rev// x 被翻转了}}returnrev}ifdfs(0,-1){// 只剩下一个根节点需要翻转无法操作return[]int{-1}}fori,rev:rangerevs{ifrev{ansappend(ans,i)}}return}funcmain(){n:7edges:[][]int{{0,1},{1,2},{2,3},{3,4},{3,5},{1,6}}start:0011000target:0010001result:minimumFlips(n,edges,start,target)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-fromtypingimportListdefminimumFlips(n:int,edges:List[List[int]],start:str,target:str)-List[int]:classEdge:def__init__(self,to:int,idx:int):self.toto self.idxidx g[[]for_inrange(n)]fori,einenumerate(edges):x,ye[0],e[1]g[x].append(Edge(y,i))g[y].append(Edge(x,i))revs[False]*(n-1)# 返回是否需要翻转 x-fa 这条边defdfs(x:int,fa:int)-bool:revstart[x]!target[x]# x-fa 是否要翻转foreing[x]:ye.toify!faanddfs(y,x):revs[e.idx]True# 需要翻转 y-xrevnotrev# x 被翻转了returnrevifdfs(0,-1):# 只剩下一个根节点需要翻转无法操作return[-1]ans[]fori,revinenumerate(revs):ifrev:ans.append(i)returnansdefmain():n7edges[[0,1],[1,2],[2,3],[3,4],[3,5],[1,6]]start0011000target0010001resultminimumFlips(n,edges,start,target)print(result)if__name____main__:main()C完整代码如下#includeiostream#includevector#includestring#includefunctionalusingnamespacestd;vectorintminimumFlips(intn,vectorvectorintedges,string start,string target){structEdge{intto,i;};vectorvectorEdgeg(n);for(inti0;iedges.size();i){intxedges[i][0],yedges[i][1];g[x].push_back({y,i});g[y].push_back({x,i});}vectorboolrevs(edges.size(),false);// 返回是否需要翻转 x-fa 这条边functionbool(int,int)dfs[](intx,intfa)-bool{boolrev(start[x]!target[x]);// x-fa 是否要翻转for(autoe:g[x]){intye.to;if(y!fadfs(y,x)){revs[e.i]true;// 需要翻转 y-xrev!rev;// x 被翻转了}}returnrev;};if(dfs(0,-1)){// 只剩下一个根节点需要翻转无法操作return{-1};}vectorintans;for(inti0;irevs.size();i){if(revs[i]){ans.push_back(i);}}returnans;}intmain(){intn7;vectorvectorintedges{{0,1},{1,2},{2,3},{3,4},{3,5},{1,6}};string start0011000;string target0010001;vectorintresultminimumFlips(n,edges,start,target);for(intv:result){coutv ;}coutendl;return0;}