《较难》就这啊😅我以为多难呢思路：拿一个队列装每一轮窗口的值，并且考虑上一个窗口的最大值是否被排出去，如果是，则重新比较队列里的值，如果不是，则只需比较新进来的值和上一个窗口的最大值，并更新最大值。 class Solution { public: int q_max(vector<int> arr) { int max = arr[0]; for (int i = 0; i < arr.size(); i++)max = (arr[i] > max) ? arr[i] : max; return max; ...

经典的用栈判断语法合法性问题 #include <stack> #include <unordered_map> class Solution { public: unordered_map<char, char> char_map = {{'(', ')'}, {'{', '}'}, {'[', ']'}}; bool isValid(string s) { stack<char> stack; for (int i = 0; i < s.size(); i++) { ...

这题要求各个操作的时间复杂度都要是常数，那就意味着min这个求最小值过程不能用遍历。（不过看题目中给的数据范围，遍历应该也过得了。）那就只能采用以空间换时间的策略了，设置一个整数数组，第i个位置记录从栈底到第i个栈位置的区间的最小值（从0开始），push和pop操作都更新以栈顶位置为区间边界的区间最小值（这里偷懒并没有在pop操作里也更新）。这就是一个最简单的动态规划。其优势就是能立刻返回栈中元素的最小值，劣势也是显而易见的，即更大的空间开销。 class Solution { public: ListNode* stack; int min_val = (1 <&l...

class Solution { public: void push(int node) { stack1.push(node); } int pop() { while (!stack1.empty()) { stack2.push(stack1.top()); stack1.pop(); } int res = stack2.top(); stack2.pop(); while (!stack2.empty()) { ...

最捞的一集，分步骤求解😅求右视图用逆序的层序遍历，可以节省一点时间。 #include <cstddef> class Solution { public: bool areAllEmpty(const vector<TreeNode*>& vec) { for (int i = 0; i < vec.size(); i++) { if (vec[i]) return false; } return true; } TreeNode* reConstruc...

通过前序可以确定根，通过根和中序可以确定左子树和右子树，然后递归构建即可。 class Solution { public: TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) { if (preOrder.empty() || vinOrder.empty()) return NULL; TreeNode* root = new TreeNode(preOrder[0]); int i; ...

怎么还有这种题啊，我以为只有想不出来思路和秒过两种题，没想到还有这种堆程序的题。。。看了题解，什么时候我也能写出来这种递归啊，简直美如画😍 class Solution { public: char* Serialize(TreeNode* root) { if (!root) return nullptr; vector<TreeNode*> query; vector<string> rec; query.push_back(root); TreeNode* tmp; ...

这递归太妙了，记录一下 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 ...

说实话，写了这么些关于树的题目，感觉树的题目就应该用递归写，只要思路想清晰，写起来真舒服。这题仔细分析一下就会发现，关键点在于，p和q一定在最近祖先的两侧或本身就是最近祖先。所以就可以自顶向下去找，如果都落在一侧，那这个结点肯定不是最近的祖先，一旦发现落在两侧（包括落在子树的根上），那这个结点就是最近的共同祖先。 class Solution { public: int lowestCommonAncestor(TreeNode* root, int p, int q) { if ((p <= root->val && q >= r...

跟上一题有点类似，如果用两层递归，时间复杂度太大。看了题解才发现可以边递归计算左右子树深度边判断是否平衡。可能平时不怎么用c++，竟然忘了引用这个功能。惭愧惭愧。。。 class Solution { public: bool judge(TreeNode* r, int& depth) { if (!r) return true; int left = 0, right = 0;//左右子树的深度 if (!judge(r->left, left) || !judge(r->rig...

总结一下经验吧，感觉还是要静下心来仔细分析题目，不能急着动笔，不然就会遇到数不尽的坑。练习的时候还可以拿不通过样例调试，实战可没有这种条件。这一题稍微想想就知道可以用层序遍历。通过检查每一层的结点分布以及这一层的层数与个数的关系来判断到该层为止是否是完全二叉树。突然想到其实不用一层一层看，直接将层序遍历当成一个整体看，只要出现过一次None结点，而后面又有非None的结点的时候就可以判断不是完全二叉树。如果一层一层看，就需要多一个判断，判断节点数不满的层是不是最后一层，而整体看就不用考虑这个。 /** * struct TreeNode { * int val; * struct T...

感觉还是有点难度的，我能想到的就三条路：递归。一开始我用递归写了一遍，发现仅仅用自顶向下的逻辑没办法排除下层以下的值比本结点大的情况，所以还得加一个变量去记录每层以各个结点为根的子树的最大值和最小值，如果这个过程也以递归来求，那时间空间成本都太大了，相当于两层循环。栈。虽然这是自底向上的逻辑，但也不好写，首先处理循环中如何不重复放入结点就很麻烦。其次，跟上面说的一样，需要用变量去记录最大最小值，记录的个数应该是2n。费劲巴拉的最后性能不好，得不偿失。转换为链表。因为二叉搜索树按特定规则转换为链表后应该是有序的，所以先转换为链表，再遍历检查就能知道原来的二叉树是否是搜索树。我这里转换代码就用的递...

用广度优先搜索的思路还是很简单的。 class Solution { public: TreeNode* Mirror(TreeNode* pRoot) { if (!pRoot) return pRoot; vector<TreeNode*> query; query.push_back(pRoot); TreeNode* p, * tmp, * l, * r; while (!query.empty()) { p = query[0]; t...

代码看起来有点繁琐了，主要是结点为None的情况无法放在加法的过程中去考虑，因为这样无法让None指针接收另一个指针的节点值，所以得从none结点的父节点就要考虑none这种情况。 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: /** * 代...