考察知识点： 树的遍历题目分析： 树中的每个节点都有机会作为特殊路径的开始位置。因为特殊路径必须是从上到下，这种先访问根节点再访问左右节点的遍历方式是先序遍历，所以从根节点开始作为开始位置，通过先序遍历，每次找到特殊路径后数量加1即可。遍历完毕后将根节点的左孩子和右孩子分别作为开始位置即可。所用编程语言： C++ /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nu...

考察的知识点：树的遍历、递归题目分析： 遍历一遍树，然后记录节点数量即可。 递归时，基准条件是root为空的情况，对应树中有0个节点。然后对每一个子树，将其左子树中的节点数量加上根节点，再加上右子树中的节点数量，递归回原树的根节点时就能知道整棵树中的节点数量。所用编程语言： C++ /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(null...

考察知识点： 递归、树的遍历 二叉搜索树的中序遍历是一个递增序列。题目分析： 中序遍历一遍即可。基准条件是root为空树，否则先遍历左子树，然后访问root节点，之后遍历右子树。所用编程语言：C++ /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public:...

考察知识点： 栈题目分析： 本题中的难点在于怎样用常数时间找到栈中的最大值。可以使用一个额外的栈来保存每一层栈中的最大值。即： 保存体重的栈和保存每一层最大值的栈共用同一个指针，当弹出栈顶元素时，最大栈也会弹出栈顶元素。这样维护好每一层的最大值，当弹出栈顶元素时就不必重新计算栈中的最大值了。所用编程语言： C++ class MaxCowStack { public: void push(int id, int weight) { stk[tt] = weight; // Max = Max >= weight ? Max : weight; ...

考察知识点： 树的遍历、递归二叉搜索树的中序遍历序列是一个递增序列。题目分析： 中序遍历一遍即可。递归的基准条件是root为空树，否则先遍历左子树，然后访问根节点，判断根节点的值是否在区间内，在区间内则加到结果中，然后遍历右子树。所用编程语言： C++ /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ clas...

考察知识点： 树的后序遍历题目分析： 我们可以首先缩小问题的规模，当只有一个节点时，路径长为0；当只有两个节点时，路径长为1。当有三个节点时，路径长为3。 当有5个节点时，发现问题开始变得复杂起来。我们最终的选择是走4 2 1 3或5 2 1 3。我们为什么这样选？因为我们知道在这棵以1为根节点的树中，左子树中的最长路径为2,右子树中的最长路径为1。如果我们能提前知道左子树和右子树中的最长单向路径就好了。 我们发现通过后序遍历的方式，能够让我们先访问左子树和右子树，最后再访问根节点。我们可以通过后序遍历记录左子树和右子树中的最长单向距离。在遍历时查看以该节点为根节点时，若加上左右子树的最长路径...

考察知识点： 先序遍历、深度优先搜索题目分析： 可以通过先序遍历的方式，每下降一个节点，deepth加1。将满足题意的节点放入vector中。满足题意的节点可能是一个树的左子树，也可能是右子树，那怎样判断这个节点该不该加入到vector中呢？ 我们先跟着进行一次先序遍历，首先左侧的节点都满足题意，我们发现此时deepth和vector的size是相同的，可以利用这一点，当size <= deepth时将节点加入。也就是说，vector中的一个下标被先占用了的话，其他节点就不能再占用这个下标，这样就能找到结果。所用编程语言： C++ /** * struct TreeNode { * ...

考察知识点：回溯题目分析： 题目想要我们用n个左括号和右括号组成一个左括号和右括号相匹配的字符串。即每个右括号匹配一个左括号，每个括号对都是左括号在左边，右括号在右边。同时结果是按照左括号较多的靠前的顺序输出。 因为第一个字符一定是左括号，我们可以以此为起点进行递归。首先每次都先尝试将左括号放入，之后尝试将右括号放入。左括号的放入条件就是字符串中左括号的个数不能大于n，有括号的放入条件是字符串中有括号的个数不能大于n，并且还不能大于左括号的个数。 注意回溯时应该恢复现场。所用编程语言：C++ #include <ios> class Sol...

考察知识点：回溯题目分析： 分两个阶段，第一个阶段是找递归的入口，第二个阶段是递归寻找童谣。递归入口只能通过循环遍历一遍数组来进行查找，一旦查找到递归入口，那么我们就开始进行递归，尝试查找整个童谣。 查找的起始位置当然是上一次在board上匹配到的位置。我们看这个位置的上下左右是否是我们当前要找的字符，如果是那么我们将要进行下一层递归，查找下一个字符。 注意一个格子只能查找一次，我们可以通过数组标记各个格子是否被查找过，注意在回溯时应该恢复现场。 当我们要查找的字符的索引大于等于word的长度，说明我们已经找到了整个童谣，直接返回true...

考察知识点：队列、广度优先搜索题目分析： 可以通过广度优先搜索，对每一个生病的牛旁边的健康的牛进行染病。如果在将所有生病的牛旁边的健康的牛染病之后，仍有健康的牛，那么说明不能将所有牛染病。如果健康的牛的数量本身就是0，那么等待0分钟就能将所有牛染病。 在广度优先搜索时，要先记录当前队列中的长度。因为每一分钟内不能访问新加入队列中的牛。再访问每一个染病的牛时，看它的上下左右四个方向上有没有健康的牛，如果有就将健康的牛染病，并记录健康牛的数量减1。当健康牛的数量为0时返回需要的分钟数。所用编程语言：C++ class Solution { public: /**...

考察知识点：广度优先搜索题目分析： 可以通过队列进行广度优先搜索。每一次将病了的牛旁边健康的牛染病，并加入到队列中。每一分钟都是看当下队列中的所有牛，新加入的牛需要到下一分钟才访问，可以通过每次查询队列的size来控制。 在每一次将病了的牛旁边健康的牛染病时，可以通过数组 int dx[4] = {1, 0, -1, 0};和 int dy[4] = {0, 1, 0, -1};来遍历四个方向，看这四个方向中哪一个方向是健康的牛，再将其染病。所用编程语言：C++ class Solution { public: /** * 代码中的类名、方法名、...

考察知识点：递归题目分析： 可以使用深度优先搜索的方式，枚举每一个字符，以每个字符为起点，查找合法的子串。 在找到结果后应按题目要求按字典序排序并去除相同的子串。所用编程语言：C++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return string字符串vector */ bool isPalindrome(string &s,...

考察知识点：回溯题目分析： 可以使用回溯法找到所有的回文子串。就是把给定的字符串分割成一个一个的回文串，可以通过回溯的方法将字符串一段一段分隔，判断每一个子串是否是回文子串。如果是回文串则找包含下一个元素的回文子串，直到原字符串结尾。 首先将该串的第一个位置作为起始位置，不断地枚举结束位置。找到满足条件的结束位置后，就需要从下一个元素开始（下一个子串必须包含该元素），找剩下的区间中满足条件的回文串集合。下图中group的目的是找满足条件的每一种情况，将每种情况加入到结果集中就得到了题目的解。 每次遇到分出来的字符串不是回文串的情况时，就不必再向下走了。...

考察知识点： 深度优先搜索、树的遍历题目分析： 首先画图考虑可能出现的结果： 第一种是两个节点一个在某个子树的左子树中，一个在右子树中： 第二种是两个节点都在某个子树的左子树中或右子树中： 首先我们应该遍历一下树，在找到p或q时返回该节点的指针。在上述例子中，如果我们从节点2开始深度优先遍历树，一旦找到节点就立刻返回该指针，则可能会产生三种情况：1. 遍历左子树时返回了非空指针，遍历右子树时也返回了非空指针。这说明当前的节点就是我们要找的节点。因为如果再比2高一层的话，p和q一定在那棵子树的同一侧，例如下图中4和10都在节点1的左子树中：2. 遍历左子树时返回了非空指针，遍历右子树时返回了空指...