算法刷题模型整理（四）

LC101 对称二叉树

解题模型：

​ 递归

核心思路：

​ 两个指针递归遍历二叉树，每次对比p->left和q->right、p->right和q->left是否相等

易错点：

• 注意空指针的情况
• 需要比较的是值而不是指针

LC104 二叉树的最大深度

解题模型：

​ DFS/BFS

核心思路：

​ 思路1：DFS，返回值为左右子树深度里的大的那个值+1

​ 思路2：BFS，相当于分层的层序遍历，每遍历完一层若队列不为空则深度+1

易错点：

• DFS注意指针为空的情况
• BFS注意子树不为空才能放进队列

LC236 二叉树的最近公共祖先

解题模型：

​ DFS

核心思路：

​ 当节点命中或左右子树有命中则返回1，否则返回0，当节点本身命中，且左右子树也有一个命中，或者左右子树都命中，这个节点就是答案

易错点：

• 第一个找到的就是答案，因为是从下往上找的，并且更上面的其它节点也不会是答案，因为不符合任何一个条件

回溯

LC077 组合

解题模型：

​ 递归

核心思路：

​ 在1~n中选k个数，递归，退出条件为k == 0，每深一层k-1，选择时从上一个数字s的后一个数开始，s初始为0

易错点：

• 循环结束条件应为i <= n - k + 1，在剩余可选择数字不够时直接退出
• dfs函数参数注意哪些可以引用

LC017 电话号码的字母组合

解题模型：

​ dfs

核心思路：

​ 字符串数组映射字母，然后简化为组合问题

易错点：

• 映射表下标从2开始，0，1为空，2才开始填字母
• 转化为下标时注意char到int的转换

LC039 组合总和

解题模型：

​ dfs

核心思路：

​ 先排序，然后进行递归，每次递归都直接从上次选取的最后一个数的位置开始，初始时为0。可以简化为二叉树，即左子树为选自己，右子树为选下一个数，递归传入target，每次传入时减去当层选取数字

易错点：

• 进入下一层递归条件，target减当前数字大于等于0，若不符合可直接退出当前层，因为已排序，后面的数字更大
• 注意哪些是引用参数

LC131 分割回文串

解题模型：

​ dfs

核心思路：

​ 使用游标法，每次都传入整个s和要操作的区块下标，然后即开始递归，每次判断一个区块，若是回文串则将当前区块后面剩余的部分传入下一层递归，最后游标等于字符串长度时即符合条件

易错点：

• 少用substr，会增加很多内存开销，游标法性能更佳
• 回文串判断函数也可以用游标法，而不是直接传子串