递归/回溯中「状态传递」

递归/回溯中「状态传递」笔记一、先记住一句话Java 只有值传递。基本类型传副本引用类型传“引用的副本”。基本类型参数每层独立引用类型参数对象共享成员变量隐式共享。二、基本类型 vs 引用类型清单基本类型8 种传副本每层独立类型例子bytebyte b 1;shortshort s 2;intint sum 0;longlong x 10L;floatfloat f 1.0f;doubledouble d 2.0;charchar c a;booleanboolean flag true;特点作为参数传进去下一层改的是副本当前层不变。不能靠参数把下层结果带上来。引用类型传“引用的副本”对象共享类别例子数组int[]、boolean[]、char[]、int[][]字符串String不可变但仍是引用类型集合List、ArrayList、LinkedList、Set、Map、Deque自定义对象TreeNode、ListNode、Node、你自己写的类包装类Integer、Long、Double、Boolean不可变其他StringBuilder、AtomicInteger、int[]包装的计数器特点作为参数传进去所有层指向同一个对象。改对象内容所有层可见。但引用变量本身是每层一份重新赋值list new ArrayList()不影响上层。⚠️ 注意String、Integer等不可变看起来像基本类型改不了内容只能重新赋值所以不能当共享可变状态用。三、三种跨层传递状态的方式方式 1参数传递voiddfs(intsum,ListIntegerpath,boolean[]used){...}状态类型效果基本类型每层独立下层改了上层看不到引用类型对象共享下层改了上层能看到适合基本类型只需要往下传如k、index、target天然回溯不用恢复。引用类型需要共享修改如used、path、ans。优点状态显式函数只看参数就知道依赖什么多次调用互不影响。缺点参数多了列表很长。方式 2成员变量classSolution{intsum0;ListListIntegeransnewArrayList();ListIntegerpathnewArrayList();boolean[]used;}适合基本类型需要跨层累计如sum、count、maxDepth。引用类型想少传参数。优点参数短代码干净。缺点隐式状态改了要手动恢复同一个对象多次调用要小心重置并发不安全。⚠️回溯时成员变量改了必须成对恢复sumx;path.add(x);dfs(...);sum-x;path.remove(path.size()-1);方式 3返回值往上抛intdfs(TreeNoderoot){if(rootnull)return0;intleftdfs(root.left);intrightdfs(root.right);returnMath.max(left,right)1;}适合自底向上汇总如树高、路径数、LCA 返回节点、子树和。每一层的结果只依赖子问题的返回值。优点无副作用最干净天然支持分治。缺点只适合“子树结果能合并成父结果”的场景回溯题里通常不适用因为回溯是“路径状态”而不是“子树汇总”。四、选择策略决策表状态推荐方式原因基本类型只往下传k、index、target参数每层独立天然回溯不用恢复基本类型需要跨层累计sum、count成员变量或int[]包装参数传不上去必须共享引用类型需要共享修改path、ans、used参数或成员变量都行对象共享参数更显式自底向上汇总树高、子树和、LCA返回值最自然无副作用不可变引用String、Integer当基本类型看待改不了内容只能重新赋值五、回溯场景的固定套路voidbacktracking(参数){if(终止条件){收集结果;return;}for(选择:本层可选集合){处理节点;// 修改共享状态backtracking(...);回溯撤销处理;// 恢复共享状态}}必须恢复的共享可变状态path.add/removeLastused[i] true/false成员变量sum / -二维数组标记board[i][j] # / 原值不用恢复的每层独立基本类型参数k - 1、target - nums[i]、index重新赋值的局部变量六、常见坑基本类型参数想跨层累计结果上层拿不到voiddfs(intsum){sumx;dfs(sum);}// 上层 sum 永远不变改成员变量或int[]。成员变量忘了恢复sumx;dfs(...);// 忘了 sum - x;下一个分支带着脏状态跑。引用类型重新赋值以为共享voiddfs(ListIntegerpath){pathnewArrayList();// 上层看不到}改内容用add/remove别重新赋值。String、Integer当共享状态不可变s c其实是新建对象上层看不到。用StringBuilder或char[]。ans.add(path)没复制ans.add(path);// 错后续 path 变了ans 里的也变ans.add(newArrayList(path));// 对快照Solution对象复用成员变量没重置力扣一般每次 new但本地/面试连续调用要手动清空ans、path、sum。七、典型题对照题目状态推荐方式46 全排列used数组参数引用共享46 全排列path、ans成员变量或参数39 组合总和target剩余值参数每层独立不用恢复39 组合总和sum累计值成员变量要恢复或参数传剩余77 组合startIndex参数只往下传236 LCA找到的节点返回值自底向上104 树高高度返回值112 路径总和剩余 target参数113 路径总和 IIpath、ans成员变量或参数path要回溯八、一句话总结基本类型参数只往下传要累计就上成员变量或包装数组引用类型参数天然共享改了要恢复自底向上汇总用返回值。回溯题优先“参数传剩余量 成员变量收集结果”少用“基本类型成员变量 手动恢复”能少一半 bug。