198. 打家劫舍你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 思路参考子集型回溯，有（1）选或不选（2）选哪个，这两种思路，对于很多动态规划问题，也

46. 全排列给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 思路数组元素各不相同，那么全排列的个数就是数组长度的阶乘。 相比组合，在排列中，元素的顺序是有区别的。 用一个数组 $path$ 记录路径上的数字（已选数字）。集合 $s$ 记录剩余未选数字。 回溯三问： 当前操作：从 $s$ 中枚举 $path[i]$ 要填入的数字 $x$。 子问

77. 组合给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 思路回顾子集型回溯，如果要从 3， 2， 1 中选出子集，按照每次选一个数的做法，可以得到一颗搜索树，搜索树每一层的数字个数是相同的，他们恰好可以表示从三个数中选择一个数的三种情况，选择两个数的三种情况和选择三个数的一种情况，这刚好就是我们要求的组合问题。 所以只需要在求子

回溯问题套路 子集型回溯0-1背包问题也可以算作一种子集型回溯。 子集本质上就是看集合的每个元素是选它还是不选它。 比如集合有两个元素，第一个元素选或者不选，有两种情况，第二个元素同理，那么总共有2*2=4种情况。 要想生成所有子集，有两种思路，区别在于当前操作是什么。如果站在输入的角度思考，那就是枚举第i个数，选它还是不选它；子问题就是从下标大于等于i的数字中构造子集；下一个子问题就是从下标大

102. 二叉树的层序遍历（广度优先搜索）给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。 思路层序遍历是一行一行地遍历。 做法1初始化一个 cur 数组，把根节点放进去，然后开始循环，再创建一个 nxt(next) 数组，遍历 cur 数组中的每个节点，把他的左右儿子都放到 nxt 数组中，如果儿子是空的就不放，把 cur 遍历完之后就得到下一

236. 二叉树的最近公共祖先给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 思路分类讨论，对于当前节点，一共有四种情况，1.它是空节点；2.它是 p；3.它是 q；4.其它情况（是否找到 p 或 q

98. 验证二叉搜索树给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下： 节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。 思路1在递归的时候，除了传入节点，还需要传入这个开区间的范围，对于每个节点，先判断它的节点值是否在开区间内，然后再往下递归，那如果往左边递归，那就把开区间

100. 相同的树给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。 思路相同的定义：首先根节点必须是相同的，然后就看左子树是否相同，右子树是否相同，这样可以看出要解决的子问题，就是左边两颗子树是否相同，以及右边两颗子树是否相同，这样就可以用递归来解决了，边界条件是如果两个子节点都是空，就返回 true，否

104. 二叉树的最大深度给定一个二叉树 root ，返回其最大深度。 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 思路1做二叉树题目的时候往往需要用到递归，不要一开始就陷入细节，而是思考整棵树与其左右子树的关系。 整棵树的最大深度 = max(左子树的最大深度，右子树的最大深度) + 1 计算左子树右子树的最大深度和计算整棵树的最大深度是相似的，分别叫做子

237. 删除链表中的节点有一个单链表的 head，我们想删除它其中的一个节点 node。 给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。 链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。 删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是： 给定节点的值不应该存在于链表中。链表中的节点数应该减少 1。node 前面的