写此系列博客的榜样来自：leetcode cookbook
套路
增量构建答案的过程，通常由递归实现
回溯三问：
- 当前操作？枚举path[i]要填入的字母
- 子问题？
- 下一个子问题
先写二叉树回溯,再做的通用回溯。二叉树型回溯和多叉树(通用型)回溯的区别就是 通用型要写for loop，而二叉树只有2个选择，所以没有for loop，直接执行dfs(node.left)和dfs(node.right).
从写代码的角度对比,几乎完全一样:
确定递归函数的意义：
1.1 def dfs(node):从上到下遍历树的每一个node 1.2 def dfs(i):从index 0开始构造这条路径
确定base case：
2.1 if node is None 所有该遍历的节点已经遍历完了(node是叶子节点的时候，就是最后一片要遍历的叶子） 2.2 if i == n 这条路径已经被填满了(i=n-1的时候，就是最后要处理的一个path格子)
确定单层递归的当前操作:
3.1 加入pathpath.append(str(node.val)) 且 进行下层递归dfs(node.left) dfs(node.right) 且恢复现场path.pop() 3.2 在for loop下加入path在for loop下: path.append(c) 且 进行下一层递归dfs(i + 1) 且恢复现场path.pop
子集型回溯
- 当前操作？
- 子问题？
- 下一个子问题
#
