1、思路  前序遍历的同时计算从根节点到当前节点路径之和，哈希表的键表示路径前缀和，值表示路径终点所在的层（因为路径只能由上自下）；  遍历过程中若在哈希表中找到curSum - targetSum，则表示已经找到一条累加和为指定值的路径，更新其路径长度；  哈希表初始化hash[0] = 0，表示第0层的路径和为0。   2、代码 #include <iostream> #include <unordered_map> using namespace std; struct TreeNode { int val; TreeNode *left, *right; Tre...

1、思路  因为遍历二叉树的递归方法实际使用了函数站，非递归的方法使用了申请的栈，两者的额外空间都与树的高度相关，所以空间复杂度为 ， 为二叉树的高度；  减少空间复杂度的难点在于从子节点返回父节点，Morris遍历利用了二叉树中大量存在的空闲节点来实现从下层到上层的遍历；  Morris遍历原理：1、若当前节点cur == nullptr，则遍历完结，否则继续下面的过程；2、若cur->left == nullptr，则cur = cur->right；3、若cur->left != nullptr，则找到cur左子树上最右的节点，记为mostRight： 3.1）若mos...

1、思路  跟普通的二叉树先序遍历和层序遍历一样，只不过用string替代了vector。  注意建树方式。   2、代码 #include <iostream> #include <string> #include <queue> using namespace std; struct TreeNode { int val; TreeNode *left, *right; TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {} }; void createTree(TreeNode*...

模板题，注意简单的建树方法。  #include <iostream> #include <vector> #include <stack> #include <algorithm> using namespace std; struct TreeNode { int val; TreeNode *left, *right; TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {} }; //建立二叉树 void createTree(TreeNode* root, int&...

1、思路  同时遍历两条有序链表，将较少的节点接到head之后；  当一条链表遍历完毕后，直接将另一条链表剩余部分全部接在后面即可。   2、代码 list_node * merge_list(list_node * head1, list_node * head2) { list_node *head = new list_node(), *p = head; while (head1 != nullptr && head2 != nullptr) //两条链表都不为空时 { if (head1->val < head2->val) //每次选择较小的节点 ...

1、思路   遍历有序环形链表，找到小于num的节点；   创建num节点，将它插入到合适的位置即可；   考虑到待插入节点的值可能比头节点更小的情况，要从链表的尾结点开始遍历。若遍历了一圈没有找到小于num的节点，则在表尾后（即表头前）新增这个num节点。   2、代码 list_node * insert_num(list_node * head, int num) { auto p = head; while (p->next != head) p = p->next; //找到尾结点 auto tail = p; while (p->next != tail &amp...

1、思路  不给链表的头结点，只给其中一个节点，要求删除这个节点（题目保证要删除的节点不是链表的尾结点）；  将下一节点的值赋给当前节点，并跳过下一节点即可。   void remove_node_wired(list_node * node) { if (node == nullptr) return; node->val = node->next->val; //赋值 node->next = node->next->next; //跳过下一节点 }

1、思路  将链表分为已排序和未排序两个部分，循环遍历未排序部分找到最小值，将其从未排序链表中删除并添加到已排序链表末尾；  为了实现删除最小值节点的操作，需要保存最小值节点的前一个节点；  时间复杂度为 ，空间复杂度为 。   2、代码 //在未排序链表中找到最小值节点的前一个节点 list_node * getSmallestPreNode(list_node *head) { list_node *smallPre = nullptr, *small = head, *pre = head, *cur = head->next; while (cur != nullptr) { i...

1、思路  用两个指针pre和cur来标记前一个节点和当前节点，若当前节点值为要删除的指定值，则将pre的下一节点指向cur的下一节点，即跳过当前节点；  时间复杂度 ，空间复杂度 。   2、代码 list_node * remove_value(list_node * head, int num) { if (head == nullptr) return head; auto pre = head, cur = head->next; //双指针 while (cur != nullptr) { if (cur->val == num) { pre->next = cu...

解法一：哈希 1、思路  遍历链表的过程中，将元素的值存入哈希表内，遇到相同值的节点跳过即可；  时间复杂度 ，空间复杂度 。   list_node * remove_rep(list_node * head) { if (head == nullptr || head->next == nullptr) return head; unordered_set<int> set; auto pre = head, cur = head->next; set.insert(head->val); //头结点不会被删除，先存入哈希表中 while (cur != nu...

1、思路  用双指针标记链表中每段为K个节点长度的首尾节点，反转当前段，保存当前段反转后的头结点newHead，递归进入下一段的反转；  若tail尾结点已经指向空，则返回链表。   2、代码 list_node* reverse(list_node* head, list_node* tail) //反转链表模板 { auto pre = head, cur = head->next; while (cur != tail) { auto ne = cur->next; cur->next = pre; pre = cur, cur = ne; } head->nex...

1、思路   先把两个链表反转，从低位开始相加；   相加完毕后，再将链表反转即可。   2、代码 list_node* reverseList(list_node* head) //反转链表 { if (head == nullptr) return nullptr; auto pre = head, cur = head->next; while (cur) { auto ne = cur->next; cur->next = pre; pre = cur, cur = ne; } head->next = nullptr; return pre; } list_n...

解法一：暴力 1、思路   把链表值全部复制到vector中，通过sort排序，然后遍历打印数值；   时间复杂度 O(N)O(N)O(N)，空间复杂度 O(N)O(N)O(N) 。   2、代码 list_node * list_partition(list_node * head, int pivot) { vector<int> v; auto p = head; while (p != nullptr) { v.push_back(p->val); p = p->next; } sort(v.begin(), v.end()); for (int &i ...

解法一：栈 1、思路  遍历链表放入栈中，弹出栈元素的同时从头遍历链表，比较栈顶元素与链表当前元素是否相等即可；  时间复杂度 ，空间复杂度 。   2、代码 list_node * check(list_node * head) { if (head == nullptr || head->next == nullptr) { cout << "true" << endl; return head; } stack<int> stk; //栈中只需要存链表节点的值即可，不用存下整个节点，节约空间 auto p = head; wh...