知识点二叉搜索树思路总的思路是遍历二叉树的每一个点，累加在范围内的值，得到答案。但是由于二叉搜索树的左子树的值一定小于根节点小于右子树的值，所以当根节点的值大于low才遍历左子树，当根节点的值小于high才遍历右子树，可以优化常数。最坏复杂度不会变。时间复杂度最坏情况下每一个点都在范围内，遍历一遍二叉树，时间复杂度为。AC code（C++） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nul...

知识点递归 最近公共祖先思路要找两个点的最近公共祖先，从根节点查找所在的子树中是否含有这两个值，假如左右子树都含有目标节点，说明它们分居两个子树中，答案是当前父节点；假如有一个子树不存在，说明两个都在另外一个子树中。时间复杂度遍历一遍二叉树 AC code（C++） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ cla...

知识点DFS 树形DP 哈希表思路树中两点的路径和可以变成这两点到根节点的路径和的差值，我们构造一个dfs函数，来获取从根节点到达当前节点的路径总和，并用一个哈希表来维护已有的不同路径和的个数，那么以当前节点为较下面端点的贡献是mp[cur - sum]计算完当前贡献后，把当前cur加入mp用于计算下面的节点。由于DFS的性质可以保证mp里面存储的都是当前节点的祖先节点信息。AC code（C++） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * Tre...

知识点树的直径 树形DP思路树的直径板子题，有两次DFS的解法和树形DP的解法，这里是树形DP的做法。我们需要用DFS得到每个节点到叶子节点的最长距离，在每个节点处用左子树的最长距离和右子树最长距离以及本节点更新答案。由于我们求的是节点数，边数应该是-1。时间复杂度每个节点遍历常数次 AC code（C++） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nul...

知识点利用翻转O(1)解决循环数组位移思路假如要把前k个数循环移动，我们可以先翻转前k个数，再翻转后n-k个数最后整个数组翻转即可实现时空复杂度时间复杂度为空间复杂度为AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @param k int整型 * @return int整型vector */ vector<int>...

知识点树形DP DFS思路答案一定是从某一个节点，到两个叶子结点的路径和。我们可以用树形DP进行解决。dfs返回从某一节点作为根节点的子树到达叶子结点的最大路径和，用经左子树和右子树的两个路径和 + 该结点的val来更新答案，然后将该结点的val加入路径后计算最大到叶子结点路径和，返回父节点。时间复杂度每个节点只遍历一次，AC Code （C++） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left...

知识点DFS 后序遍历 中序遍历思路后序遍历是顺序是“左右中”，中序遍历顺序是“左中右”。因此每次找到对应序列的后序遍历的最后一个数作为根节点，然后找到对应的左右子树的对应的范围，把问题化为原问题的子问题，用递归解决。时间复杂度最差情况是一条链，时间复杂度为AC code（C++） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }...

知识点DFS 先序遍历 中序遍历思路先序遍历是顺序是“中左右”，中序遍历顺序是“左中右”。因此每次找到对应序列的先序遍历的第一个数作为根节点，然后找到对应的左右子树的对应的范围，把问题化为原问题的子问题，用递归解决。时间复杂度最差情况是一条链，时间复杂度为AC code（C++） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * };...

知识点中序遍历思路先中序遍历获取到指针的先后顺序，之后重新建立指针间的关系。时间复杂度每个节点访问常数次，AC code（C++） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定...

知识点先序遍历思路先先序遍历获取到指针的先后顺序，之后重新建立指针间的关系。时间复杂度每个节点访问常数次，AC code（C++） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定...

知识点完全二叉树思路完全二叉树的父节点编号若为x，那么左儿子的编号是x << 1; 右儿子的编号为x << 1 | 1遍历二叉树，取最大的编号即可，编号从1开始。时间复杂度和节点个数成正比，AC code（C++） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { p...

知识点摩尔投票法思路题目要求求众数，我们可以排序后找到中间元素，这样时间复杂度为。用摩尔投票法可以将复杂度降到，主要思想就是像投票一样，优势牛种会抵消其他的牛种的总和。AC code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int majority_cow(vector<int>& nums) ...

知识点数组模拟思路因为原数组非递减，我们只需要判断相邻的元素是否相等，如果不相等则可以加入结果数组。由于结果数组的大小一定小于等于原数组，所以可以在原数组上做修改。时间复杂度遍历一遍数组，AC code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int remove_duplicates(vector<int&...

知识点二叉搜索树思路二叉搜索树的中序遍历可以得到有序序列，因此跑一下中序遍历即可，时间复杂度为AC Code （C++） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ #include <functional> class Solution { public: /** * 代码中的类名、方法...