Bin's Tech Diary

Tree DFS Tree DFS Tree上的DFS分为两种（Divide Conquer + Traversal和纯Divide Conquer） 建立当前/用全局变量（根据不同的方式） root 为 空 （ 返回 什么/ 更新 指针） 左 节点和 右 节点 都 为 空 ，用 root 构建 当前 解（ 返回 什么/ 更新 指针） 左 节点和 右 节点 不 为 空 ，用 左右 构建 当前 解 返回 当前 /选择 左 ， 右 ， 中 Divide Conquer + Traversal 不同 一般 没有 全局变量， 创建当前 变量作为当前最终解 通过 左 节点的最终解和 右 节点的最终解， 计算 并更新 当前 变量 判断 左 节点的最终解， 右 节点的最终解， 当前 变量，在三个解中 选择 一个 作为当前层的最终解 返回 更新传入的参数指针 （ 有时会单独建立 class Result 类 ） 流程 建立 当前 变量（不一定第一步） root 为 空 （ 返回 什么） left 节点和 right 节点 都 为 空 ，用 root 构建 当前 解（ 返回 什么/ 更新 指针） left 节点和 right 节点 不 为 空 ，用 左右 解 leftResult , rightResult 计算 当前 解 选择 符合的解 比较 （ leftResult ， rightResult ， result ） + 选出 合适的解 直接使用 ：当前解 使用 选中的解 返回 更新 传入的指针 例题（Minimum Subtree） public class Solution { class Result { TreeNode minSubtree; int minSum; int sum; Result(TreeNode minSubtree, int minSum, int sum) { this.minSubtree = minSubtree; this...

Implicit Graph DFS Implicit Graph DFS Combinations（组合） 需要注意的是以下几点： 空值 ：看清题目，如果当 nums 的个数为 0 的时候，需要不需要加入空列，如果需要就不能在判断空条件下加入 .length 排序 ：在做组合类题目之前一定要确定这个 nums 是个有序的数组，如果不是就需要排序 dfs() ：一般都是 dfs(collection, [condition], index, level result, final results) 添加result到results中 ：如果没有特殊条件直接添加，否则在特殊条件下 加入 并 返回 return for循环 ：注意 i 的初始值是 index for循环体 ：dfs老套路，加入，再 dfs ，再删去，dfs时，注意 [condition] 是否需要改变， index 传的是和 i 相关的，如果不可以重复传入 i + 1 ，如果可以重复传入 i SubSets（最简单的Combination） public class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> results = new ArrayList<>(); if (nums == null) { return results; } // 一定要排个序之后再做 Arrays.sort(nums); dfs(nums, 0, new ArrayList<Integer>(), results); return results; } private void dfs(int[] nums, int index, List<Integer> result, List...