吴江做网站公司,wordpress怎么在底部调用友情链接,网页制作入门教程视频,无锡网站制作公司1.回溯
回溯可以视为递归的拓展#xff0c;有着明确的解题模板。
很大的不同之处是有一个撤销处理结果的操作#xff0c;但是大框架就是遍历 N 叉树。
回溯主要解决暴力枚举都解决不了的问题。
回溯模板#xff1a;
void backtracking(参数) {if (终止条件) {存放结果;…1.回溯
回溯可以视为递归的拓展有着明确的解题模板。
很大的不同之处是有一个撤销处理结果的操作但是大框架就是遍历 N 叉树。
回溯主要解决暴力枚举都解决不了的问题。
回溯模板
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素(画成树就是树节点孩子的大小)) {处理节点;backtracking();回溯撤销处理结果;}
}回溯完整代码示例返回 1 到 n 中所有可能的 k 个数的组合
public ListListInteger combine(int n, int k) {ListListInteger resultList new ArrayList();if (k 0 || n k) {return resultList;}DequeInteger path new ArrayDeque();dfs(n, k, 1, path, res);return res;
}public void dfs(int n, int k, int startIndex, DequeInteger path, ListListInteger resultList) {if (path.size() k) {resultList.add(new ArrayList(path));return;}for (int i startIndex; i n; i) {path.addLast(i);dfs(n, k, i 1, path, resultList);path.removeLast();}
}2.回溯题目输出二叉树的所有路径
原题力扣257.
class BinaryTreePaths {ListString ans new ArrayList();public ListString binaryTreePaths(TreeNode root) {dfs(root, new ArrayList());return ans;}private void dfs(TreeNode root, ListInteger temp) {if (root null) {return;}temp.add(root.val);if (root.left null root.right null) {ans.add(getPathString(temp));}dfs(root.left, temp);dfs(root.right, temp);temp.remove(temp.size() - 1);}private String getPathString(ListInteger temp) {StringBuilder sb new StringBuilder();sb.append(temp.get(0));for (int i 1; i temp.size(); i) {sb.append(-).append(temp.get(i));}return sb.toString();}
}3.回溯题目路径总和问题
原题力扣113.
class PathSum {ListListInteger res new ArrayList();public ListListInteger pathSum(TreeNode root, int targetSum) {LinkedListInteger path new LinkedList();dfs(root, targetSum, path);return res;}public void dfs(TreeNode root, int targetSum, LinkedListInteger path) {if (root null) {return;}targetSum - root.val;path.add(root.val);if (targetSum 0 root.left null root.right null) {res.add(new LinkedList(path));}dfs(root.left, targetSum, path);dfs(root.right, targetSum, path);path.removeLast();}
}如果对您有帮助请点赞关注支持我谢谢 ❤ 如有错误或者不足之处敬请指正 ❤ 个人主页星不易 ❤ 算法通关村专栏不易|算法通关村 ❤
