递归、遍历、分治

递归、深搜、回溯

Recursion DFS Backtracking

区别与联系

递归 Recursion

递归函数：函数自我调用

递归算法：大问题的结果依赖于小问题的结果，于是先用递归函数解决小问题

一般我们说的递归指的是递归函数

深度优先搜索

可以使用递归函数来实现

也可以不用递归函数，如自己通过一个手动创建的Stack

回溯

• 回溯法：就是深度优先搜素算法
• 回溯操作：递归函数在回到上一层递归调用处的时候，一些状态参数需要调回调用之前的值，这个操作就是回溯；调用前状态参数是什么样，递归后都改回来

list、数组这些往往需要自己回溯过去

（本质上dfs就会有回溯，只是普通的dfs回溯当前的节点是操作系统实现的非递归的dfs是自己写栈去回溯的）

遍历与分治

遍历：一个小人拿着记事本走遍所有的节点

分治：分配小弟去做子任务，自己进行结果汇总

遍历法

所有路径都走一遍，不利用返回值

分治

会利用return（返回值）方法

本质上是后序遍历

问题可分割，拆分成同样的子问题

拆开来左右两边不能有交集

分治法模板：

百分之90的题不需要单独处理叶子结点，因为可以直接向空进行调用

例题：判断二叉树是否平衡

需要返回多个值时，采用定义类的方法

什么时候需要手动回溯、什么时候不需要

找点、找路径

回溯可以避免对象复制造成的内存浪费