基本思路：二叉搜索树要转换成排序链表，必然是左中右的中序遍历函数返回值是双向链表的头节点，而每次遍历节点需要的是当前节点中序遍历下的先驱节点，所以需要一个额外指针bef记录先驱节点先按照左中右的遍历顺序遍历左子树，然后将先驱节点与当前节点连接，此时需要遍历右子树了，所以需要让先驱节点指向当前节点，再遍历右子树处理边界问题class Solution { public: TreeNode* bef = nullptr; TreeNode* Convert(TreeNode* pRootOfTree) { if (!pRootOfTree) return nullptr; TreeNode* l ...

自己思考只想出hash表一种解法，参考精华题解的思路给出不使用额外空间的解法：第一次遍历：复制：在原链表的每一个节点后插入使用该节点复制的新节点，这样原链表节点的next指向其复制的节点，而复制节点的next指向原链表节点的下一个节点。第二次遍历：处理random指针：如果原链表节点的random指针为空，则其next节点指向的复制节点的random指针也设置为空；否则指向原链表节点->random->next，即为原链表节点的random指针的复制节点。第三次遍历：分离两个链表，因为不分离会判错“原链表不可用”。class Solution { public: RandomLis...

基本思路：寻找所有满足条件路径的二叉树遍历问题一律尝试用void返回值的dfs正常的遍历模板，如果遍历到当前root->val==target时判断其是否为叶子节点，如果是则在res集合中添加一条路径；如果不是叶子节点，因为二叉树中可能有负数，所以从当前节点到叶子节点的路径可能为0，最终仍然得到一条满足条件的路径，所以还需要继续遍历而不能直接return。class Solution { public: void dfs(vector<vector<int>>& res, vector<int>& path, TreeNode* roo...

基本思路：后序遍历的顺序是左右中，所以能确定的是数组最后一个数一定是根节点的值二叉搜索树的性质是左子树的值都小于根节点的值，而右子树的值都大于根节点的值可以根据这个性质尝试将数组划分为三块，从左到右分别是小于根节点的部分（左子树）、大于根节点的部分（左子树）、根节点，如果划分失败则直接返回false子数组可以递归求解，结束条件是数组中只有一个或更少的元素sequence为空时需要返回false，需要特殊判断class Solution { public: bool VerifySquenceOfBST2(vector<int> sequence, int l, int r) { i...

很简单的BFS层序遍历，基本操作了。借助队列存储当前层的节点的非空子节点。class Solution { public: vector<int> PrintFromTopToBottom(TreeNode* root) { if (!root) return {}; queue<TreeNode*> q; vector<int> res; q.push(root); while (!q.empty()) { auto now = q.front(); q.pop(); res.push_back(now->val); if (now->left...

基本思路：用栈模拟，如果满足序列指针就在popV上右移，最后如果指针移到了popV末尾，就说明满足条件。class Solution { public: bool IsPopOrder(vector<int> pushV,vector<int> popV) { stack<int> st; int i = 0, n = popV.size(); for (auto &j: pushV) { st.push(j); while (!st.empty() && st.top() == popV[i]) { st.pop(); i++; }...

基本思路：维护两个栈，一个栈正常进出，一个栈单调递减，如果当前push的值大于top，则直接push top值而不是当前push的值。优化思路：维护一个栈，每次push时同时push当前最小值与当前值两次即可。为了避免频繁操作取最小值，用int变量记录当前的最小值。class Solution { public: stack<int> st; int mn = INT_MAX; void push(int value) { if (value < mn) mn = value; st.push(mn); st.push(value); } void pop() { st.po...

class Solution { public: vector<int> printMatrix(vector<vector<int> > matrix) { vector<int> res; int m = matrix.size(), n = matrix[0].size(); int layer = min((m + 1) / 2, (n + 1) / 2); for (int k = 0; k < layer; k++) { if (m - 2 * k == 1) { for (int j = k; j < n - k; j+...

递归，先交换左右子树，然后对左右子树递归求解。Morris遍历算法太复杂了，就不强求常数空间复杂度了。。。class Solution { public: TreeNode* Mirror(TreeNode* pRoot) { if (!pRoot) return nullptr; swap(pRoot->left, pRoot->right); Mirror(pRoot->left); Mirror(pRoot->right); return pRoot; } };

分为三种情况：pRoot1->val == pRoot2->val：需要检查pRoot2的左子树、右子树是否分别是pRoot1的左子树、右子树的子树，如果都是则返回true，否则还有可能是情况2、3。pRoot2是pRoot1左子树的子树，递归调用即可。pRoot2是pRoot1右子树的子树，递归调用即可。有一点需要注意的是，约定nullptr不是任何树的子树，这就导致了在pRoot2为单节点时需要特殊处理，否则会返回错误的值。我们在pRoot1->val == pRoot2->val当中进行处理，只有当pRoot2的左右子树不为空时才进行递归调用。class Solu...

链表问题为了解题方便，一般都会建立伪头节点dummyhead。其他部分按照归并排序一样比较并尾部插入就行了。如果有一个指针指向nullptr，那么另一个指针所指链表剩下的数一定都要大于当前尾部的数，直接尾部插入即可。/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { ListNode* dumm...

递归：函数返回的是反转后的头节点，即固定为原链表中最后一个节点，所以当前函数的返回值应该与递归函数的返回值是一样的。反转之后应该由原链表中pHead->next指向的节点指向pHead，同时考虑pHead是反转后尾部的情况，应该把pHead->next置为nullptr。class Solution { public: ListNode* ReverseList(ListNode* pHead) { if (!pHead || !pHead->next) return pHead; ListNode* newhead = ReverseList(pHead->next)...

快慢指针可以做到一次遍历，需要返回倒数第k个节点，我们可以看做当快指针now指向链表末尾的nullptr时，慢指针bef正好指向倒数第k个节点，所以需要一开始先让快指针now移动k个节点。为了方便处理，设置一个dummyhead作为伪头节点，bef和now都从dummyhead出发。因为样例中存在k越界的情况，针对这部分需要加入条件额外判断。class Solution { public: ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { if (!pListHead) return nullptr; if (k &l...

本来以为需要时间复杂度O(n)，空间复杂度O(1)的解法，实在没想出来去看了官方题解，结果还是需要n方的时间复杂度。。。class Solution { public: void reOrderArray(vector<int> &array) { int i = 0; for (int j = 0; j < array.size(); j++) { if (array[j] % 2) { int tmp = array[j]; for (int k = j - 1; k >= i; k--) { array[k + 1] = array[k]; } array...