一、递归回溯

递归的体现就是方法调用自己本身。

递归回溯的方法体书写套路

  1. 递归的终止条件
  2. 递归
  3. 回溯

主要可以玩出花来的是 1、3 两部分，第 2 部分的递归就只是调用方法！

第一部分：递归的终止条件

  • 递归方法是**处理业务**的：如果递归的目的仅仅是“搞事情”也就是处理业务，而没有判断对错，那第一部分做的事就很简单，就是只给出处理业务完成时候的、或是想完成但是完成不了的情况的终止条件就行了。（力扣06）
  • 递归方法是**判断对错**的：而如果递归的目的是需要判断对错的，那这一部分就是重点了，递归的终止条件就一定得包含正确时候的条件以及错误时候的条件！（剑指 Offer 28、剑指 Offer 26）

第二部分：递归

  • 这个部分其实最简单，就是递归原方法，不要想太复杂了！唯一需要思考的就是传入的参数。

第三部分：回溯

  • 递归方法是**处理业务**的：如果递归方法是属于处理业务的话，那主要就是在回溯这一部分进行处理。
  • 递归方法是**判断对错**的：如果递归方法是属于判断对错的话，那回溯这一部分就简单了，仅仅只是返回对错的结构，并且回溯部分还可以直接和递归部分写一起！像下面这样：
    1. return recur();

二、二叉树的遍历

一轮遍历**一颗**二叉树

  • 先序遍历：要对二叉树的根节点干什么 —> 递归调用原方法(根节点的左子节点) —> 递归调用原方法(根节点的右子节点)
  • 中序遍历：递归调用原方法(根节点的左子节点) —> 要对二叉树的根节点干什么 —> 递归调用原方法(根节点的右子节点)
  • 后序遍历：递归调用原方法(根节点的左子节点) —> 递归调用原方法(根节点的右子节点) —> 要对二叉树的根节点干什么

精华就是：什么时候遍历就把要对根节点干什么放在哪！

另外：对根节点干什么也可以是去调用一个方法，或者将根节点作为参数传入一个方法（两种情况：1. 传入根节点的左右子节点 2. 传入根节点，再传入一颗别的树的根节点），一般这种情况就是要去同时遍历两颗二叉树了。

一轮遍历**两颗**二叉树（以先序遍历为例）

要对树 A 的当前根节点和树 B 的当前根节点做什么 —> 递归调用原方法 ( 树 A 的左子节点，树 B 的左子节点 ) —> 递归调用原方法 ( 树 A 的右子节点，树 B 的右子节点 )

或者

要对树 A 的当前根节点和树 B 的当前根节点做什么 —> 递归调用原方法 ( 树 A 的左子节点，树 B 的右子节点 ) —> 递归调用原方法 ( 树 A 的右子节点，树 B 的左子节点 )

又或者

要对树 A 的当前根节点和树 B 的当前根节点做什么 —> 递归调用原方法 ( 树 A 的右子节点，树 B 的左子节点 ) —> 递归调用原方法 ( 树 A 的左子节点，树 B 的右子节点 )

所以，同时遍历两颗二叉树无非就上面的3种情况，根据题目要求来决定怎么递归传参就行了！

所以遍历二叉树的主要难点在于

  1. 从**什么节点开始遍历多少颗**二叉树；
  2. 如果同时遍历两颗二叉树，那么下次递归传进去的两个参数分别是两颗树当前节点的左右子节点的以下哪种组合呢？
    1. 左左&&右右
    2. 左右&&右左
    3. 右左&&左右

比如：

  • 剑指 Offer 26：从 A 树的根节点和 B 树的根节点开始同时遍历两颗二叉树；依据题目要求，只需左左&&右右的传进去就可以了。

  • 剑指 Offer 28：从根节点**的左右子节点开始同时遍历两颗二叉树；依据题目要求，要使用左右&&右左**作为下次递归的参数传递形式，只有这样才能判断两颗树是否对称。

SO，做题的思路是？

首先判断该题需要遍历几颗二叉树才能完成：

  • 需要遍历两颗二叉树：好好斟酌需要传进去的两个参数，是一颗树的左右子节点作为两颗树还是两颗不同的树。
  • 只需遍历一颗二叉树：简单。

然后就是判断遍历是**处理业务的还是判断对错**的：

  • 处理业务的：首先终止条件先摆上去，就是该业务处理不了的情况；然后就直接套二叉树的遍历公式。假设是先序遍历：终止条件 —> 对当前节点干什么 —> 遍历左子树 —> 遍历右子树
  • 判断对错的：正确的和错误的终止条件都摆上去，主要是判断错误的情况，但是正确的要先摆上去；然后就直接遍历左子树，接着遍历右子树。（可以看到，正确和错误的情况就是对当前节点干什么了，只不过更简单了）

三、二叉搜索树的性质

  • 正常**中序遍历为递增**：左—>根—>右

  • 反序**中序遍历为递减**：右—>根—>左

  • 先序、中序、后序遍历二叉树其实就是 DFS

  • 而层序遍历二叉树就是 BFS （需要借助队列）


四、二分查找

二分查找这么写 ：while( l <= h ) 时，退出循环一定只有两种可能：

1. nums[m] 就是要找的数，返回即可，提前退出循环。

2. l 和 h 互相越过彼此，while 循环正常退出，此时 nums[l] 或 nums[h] 一定是有一个是满足题目要求的，返回即可。

一般算法题往往是第二种情况比较多，算法题不会明显地给你一个数去找，通常会很隐晦。如《剑指 Offer》11. 旋转数组的最小数字：https://leetcode-cn.com/problems/

！！！！
有点感觉了！
如果二分查找使用 while( l <= h ) 那循环体中所有的 if 或 else if 后的条件绝大多数都是 m+ 1 或 m - 1（当然，有些不是，因为数字可能存在重复数字，比如剑指 Office 11） 最后的结果要么在 l 要么在 h ，l 和 h 一定会彼此越过，最后总是 l 或者 h 其中一个是正确答案！典型的就是《剑指 Office》53 II. 0 ~ n-1 中缺失的数字！https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/
！！！