个人见解
回溯是一种算法思想
递归是一种算法结构
使用递归的代码 都可以转化为迭代
一部分可以用一次次入栈出栈的过程(没有任何好处)
一部分可以优化成从小向大求解即动态规划(空间换时间)
1. 回溯 (Backtrack) —— 算法思想
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
使用回溯算法的时候，需要多使用剪枝函数，剔除一些无用的条件进行优化！
回溯的思路基本如下：当前局面下，我们有若干种选择，所以我们对每一种选择进行尝试。如果发现某种选择违反了某些限定条件，此时 return；如果尝试某种选择到了最后，发现该选择是正确解，那么就将其加入到解集中。
如何想回溯？
选择 (Options)
限制 (Restraints)
结束条件 (Termination)
2. 递归 (Recursive) —— 算法结构
程序调用自身的编程技巧称为递归（ recursion）。 递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
通常来说，为了描述问题的某一状态，必须用到该状态的上一个状态；而如果要描述上一个状态，又必须用到上一个状态的上一个状态…… 这样用自己来定义自己的方法就是递归。
如何写递归？
1.找到如何将大问题分解为小问题的规律，定义函数（不用管函数内部的实现！）
2.通过规律写出递推公式（这个最难了，多刷题！）
3.通过递归公式的临界点推敲出终止条件（一定要防止死循环）
递归的优化
1.优化掉重复计算，可以考虑用哈希表或数组等存储计算好的子问题的值。
2.考虑自底向上（其实就是递推），主要解决递归情况下栈空间不够的问题，如斐波拉契数列的解决。
3、从 思想 到 结构
我们在路上走着，前面是一个多岔路口，因为我们并不知道应该走哪条路，所以我们需要尝试。尝试的过程就是一个函数。
我们选择了一个方向，后来发现又有一个多岔路口，这时候又需要进行一次选择。所以我们需要在上一次尝试结果的基础上，再做一次尝试，即在函数内部再调用一次函数，这就是递归的过程。
这样重复了若干次之后，发现这次选择的这条路走不通，这时候我们知道我们上一个路口选错了，所以我们要回到上一个路口重新选择其他路，这就是回溯的思想。
4、LeetCode相关题目
437.路径总和3 使用栈实现
思路：父节点的所有可能和 + 当前节点的和 == 给定sum？
递归为：求父节点的所有可能和。root的所有可能和只有它本身val。
广度遍历思路。用两个栈分别保存当前节点和父节点的所有可能和，指针同步移动。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int pathSum(TreeNode root, int sum) {
if(root == null){
return 0;
}
List<TreeNode> tree = new ArrayList<>();
List<int[]> nodeSums = new ArrayList<>();
//初始化第一个节点
tree.add(root);
nodeSums.add(new int[]{});
int i = 0;
int result = 0;
while(i < tree.size()){
TreeNode curNode = tree.get(i);
int[] parentSums = nodeSums.get(i);
int[] curSums = new int[parentSums.length+1];
for(int k = 0 ; k < parentSums.length ;k++) {
curSums[k] = parentSums[k] + curNode.val;
if(curSums[k] == sum){
result++;
}
}
if(curNode.val == sum){
result++;
}
curSums[curSums.length-1] = curNode.val;
if(curNode.left != null){
tree.add(curNode.left);
nodeSums.add(curSums);
}
if(curNode.right != null){
tree.add(curNode.right);
nodeSums.add(curSums);
}
i++;
}
return result;
}
}
113 路径总和2 使用子函数实现
一个典型的递归。注意两点：
1、跳出递归返回到上层时，把路径的最后一个val remove掉。（回溯到上一步的结果）
2、list是引用，添加到result的时候要new一个新的。
class Solution113 {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new ArrayList<>();
ergodic(root,new ArrayList<>(),sum,result);
return result;
}
public void ergodic(TreeNode root, List<Integer> path,int sum, List<List<Integer>> result){
//终止条件1
if(root == null){
return;
}
path.add(root.val);
if(root.left == null && root.right == null){
if(sum == root.val){
result.add(new ArrayList<>(path));
return;
}
}
if(root.left != null){
ergodic(root.left,path,sum-root.val,result);
path.remove(path.size()-1);
}
if(root.right != null){
ergodic(root.right,path,sum-root.val,result);
path.remove(path.size()-1);
}
}
}
网友评论