知识点DFS 遍历二叉树思路这道题题面很迷惑，看样例是找到从左到右的叶子结点。先序遍历二叉树，找到叶子结点则加入答案。只要先遍历左子树，再遍历右子树，就能从左到右得到答案。时间复杂度遍历一遍二叉树，时间复杂度为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: /*...

知识点DFS 遍历二叉树思路先序遍历二叉树，记录每一层访问的第一个值，即为答案。时间复杂度遍历二叉树，每个点至多遍历一次，时间复杂度为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: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值...

知识点层序遍历思路层序遍历得到每一层的val之和以及总个数。最后计算平均值。时间复杂度层序遍历，每个点只遍历一次，时间复杂度为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: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定...

知识点二叉树思路自顶向下遍历二叉树，维护长度，到叶子节点时更新答案，注意空节点长度为0。时间复杂度每个节点只会遍历一次，时间复杂度为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: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值...

知识点DFS思路自顶向下去维护从根节点到子节点的路径和，当子节点为叶子节点时更新答案。注意当res已经为true或者路径和已经大于target时的及时剪枝。时间复杂度每个节点至多访问一次，时间复杂度为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: /** * ...

知识点DFS multiset思路将任意节点到它的子节点的路径，拆分为任意子节点到根节点的路径 - 任意节点到根节点的路径。我们在dfs的过程中，用multiset维护根节点这个节点的祖先节点的和，去查找是否有满足要求的根节点到其祖先节点的合法路径。注意sum超过target及时剪枝。时间复杂度遍历每个节点最多n次，每次需要在multiset中查询的复杂度为总的时间复杂度为 AC code（C++） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(i...

知识点栈思路判断括号序列，可以建一个栈，遇到左括号将其压栈，遇到右括号则取出栈顶元素看是否匹配，如果栈为空或者栈顶元素不匹配则返回false，都匹配好后不可以剩下左括号不匹配，验证栈是否为空。时间复杂度只有遍历一遍字符串，时间复杂度为AC code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return bool布尔型 */ bool is_valid_cow_communication(string s) { stack<cha...

知识点后缀表达式 栈思路后缀表达式求值，可以一个栈来记录数字，每当遇到预算符号，取出栈顶的两个数字进行运算，把结果重新入栈。最后的栈顶即为全部的计算结果。时间复杂度只遍历了一遍数组，每次出入栈的次数是常数次，时间复杂度为AC code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param tokens string字符串vector * @return int整型 */ int calculatePostfix(vector<string>& tokens)...

知识点完全二叉树 层序遍历思路题目要求统计0和1的数量，分别在根节点的左右子树建立完全二叉树，然后返回根节点。我们遍历数组统计0和1的个数，之后利用层序遍历（BFS）的方法建立完全二叉树，并返回根节点作为答案的左右子树。具体见代码。时间复杂度由于只会建立n个节点并每个节点遍历一次，时间复杂度为AC code （C++） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(null...

知识点二叉树 递归思路二叉树的最大深度，等于左右子树的最大深度中的较大值+1；因此可以先求子树的最大深度，而这是一个和原问题一样的子问题，可以用递归解决。递归终点是空节点，深度为0。时间复杂度只遍历一遍二叉树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: /*...

知识点二叉搜索树思路求二叉搜索树的第k大值。二叉搜索树的中序遍历是递增序列，我们可以稍作修改，先遍历右子树，再根节点，再左子树，即可得到递减序列。当遍历的节点数到达k时，更新答案并及时剪枝。时间复杂度由于及时剪枝，时间复杂度为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...

知识点二叉搜索树思路验证二叉搜索树，需要验证左右子树是不是都是BST。然后再判断当前值是不是比左子树的所有值都大，比右子树所有值都小，实现上只需要验证左子树，因为如果右子树不满足条件，会在遍历右子树的时候不满足条件。时间复杂度遍历一遍二叉树，时间复杂度是线性的 AC code （C++） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ ...

知识点二叉搜索树思路要求出二叉树中第k小的值，二叉搜索树的中序遍历得到的是递增序列，因此只要跑中序遍历，搜索个数达到k后更新答案并及时剪枝。时间复杂度由于及时剪枝，总体时间复杂度是AC code （C++） /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ #include <queue> class Solution { p...