代码随想录

一、数组

704.二分查找

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
int center = 0; // 二分位置
while (left <= right) {
center = (left + right) / 2;
if (nums[center] == target) return center;
if (nums[center] > target) right = center - 1;
if (nums[center] < target) left = center + 1;
}
// --查找失败--
return -1;
}
};
  • 时间复杂度:O(log n)
    分析:2x=nx=log2nO(logn)2^x = n \to x = log_2n\to O(log\,n)
  • 空间复杂度:O(1)
    ?怎么分析的

27.移除元素

力扣题目链接

1、暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int nowLength = nums.size(); // 记录现在长度
for (int i = 0; i < nowLength; i++) {
// --逐个查找--
if (nums[i] == val) {
// --删除元素--
for (int j = i; j < nowLength - 1; j++) {
nums[j] = nums[j + 1];
}
// --改变上界--
nowLength--;
// --由于数组左移,所以再次查看当前位置--
i--;
}
}
// --返回删除后的长度--
return nowLength;
}
};
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)

2、快慢指针

27.移除元素-双指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int len = nums.size(); // 执行一次
int slow = 0;
// --看n次,值为val的舍弃(即需要值不为val的选出来放到新位置(slow)上)--
for (int fast = 0; fast < len; fast++) {
if (nums[fast] != val) {
nums[slow++] = nums[fast];
}
}
return slow;
}
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

977.有序数组的平方

力扣题目链接

1、平方后排序

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int len = nums.size();
for (int i = 0; i < len; i++) {
nums[i] = nums[i] * nums[i];
}
// --快排--
sort(nums.begin(),nums.end());
return nums;
}
};

时间复杂度:O(nlogn)

2、双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int len = nums.size();
// --长度为len,初值为0--
vector<int> ans(len, 0);
int cnt = len;
int i = 0, j = len - 1;
while(i <= j) {
// --前进左边--
if (nums[i] * nums[i] > nums[j] * nums[j]) {
ans[--cnt] = nums[i] * nums[i];
i++;
}
// --前进右边--
else {
ans[--cnt] = nums[j] * nums[j];
j--;
}
}
return ans;
}
};
  • 时间复杂度:O(n)

209.长度最小的子数组

力扣题目链接

快慢指针(滑动窗口)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int len = nums.size();
int fast = 0, slow = 0;
int sum = 0; // 总和
int ans = 0x7fffffff;
for (; fast <= len; fast++) {
// --和小于target,加上右边--
if (fast < len && sum < target) {
sum += nums[fast];
// printf("[sum:%d slow:%d, fast:%d, ans=%d]\n", sum, slow, fast, ans);
continue;
}
// --和大于等于target,最小值更新;减去左边,slow向前移动,fast暂时不动--
if (sum >= target) {
ans = (fast - slow) < ans ? (fast - slow) : ans;
sum -= nums[slow++];
fast--;
// printf("[sum:%d slow:%d, fast:%d, ans=%d]\n", sum, slow, fast, ans);
}
}
if (ans < 0x7fffffff) return ans;
else return 0;
}
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

59.螺旋矩阵II

力扣题目链接

1、一个一个看,走满就换方向

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class Solution {
public:
enum Direction {RIGHT, DOWN, LEFT, UP}d;
// --是否越界--
bool isOver(int x, int y, int maxX, int maxY) {
if (x < 0 || y < 0 || x >= maxX || y >= maxY) return true;
return false;
}
// --转向--
Direction changeDirection(Direction d) {
switch (d) {
case RIGHT: d = DOWN; break;
case DOWN: d = LEFT; break;
case LEFT: d = UP; break;
case UP: d = RIGHT;break;
}
return d;
}
vector<vector<int>> generateMatrix(int n) {
vector<vector<int> > ans(n, vector<int>(n, 0)); // n*n,初值为0
d = RIGHT;
int x = 0, y = 0;
for (int i = 1; i <= n * n; i++) {
// --{延伸}或者{转向 + 暂停一次位置}
switch (d) {
case RIGHT:
if (!isOver(x, y, n, n) && ans[x][y] == 0) {
ans[x][y] = i;
y++;
}
else {
d = changeDirection(d);
// printf("1(%d,%d,[%d])\n", x, y, d);
i--;
// --放到正确的位置上--
y--; x++;
}
break;
case DOWN:
if (!isOver(x, y, n, n) && ans[x][y] == 0) {
ans[x][y] = i;
x++;
}
else {
d = changeDirection(d);
// printf("2(%d,%d,[%d])\n", x, y, d);
i--;
// --放到正确的位置上--
x--; y--;
}
break;
case LEFT:
if (!isOver(x, y, n, n) && ans[x][y] == 0) {
ans[x][y] = i;
y--;
}
else {
d = changeDirection(d);
// printf("3(%d,%d,[%d])\n", x, y, d);
i--;
// --放到正确的位置上--
y++; x--;
}
break;
case UP:
if (!isOver(x, y, n, n) && ans[x][y] == 0) {
ans[x][y] = i;
x--;
}
else {
d = changeDirection(d);
// printf("4(%d,%d,[%d])\n", x, y, d);
i--;
// --放到正确的位置上--
x++; y++;
}
break;
}
}
return ans;
}
};
  • 时间复杂度:O(n^2)

2、分圈,一圈看四条边【代码随想录】

二、链表

203.移除链表元素

力扣题目链接

增加哨兵节点(养成删除内存的习惯)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
// --初值为空的情况--
if (!head) return nullptr;
// --增加一个哨兵节点--
ListNode* head0 = new ListNode;
head0->next = head;
ListNode* tmp = head0;
// --遍历--
while (tmp) {
// --删除--
if (tmp->next && tmp->next->val == val) {
tmp->next = tmp->next->next;
continue; // 不然会跳判
}
tmp = tmp->next;
}
return head0->next;
}
};
  • 时间复杂度:O(n)

707.设计链表

力扣题目链接

遇到tmp->next,还是判一下tmp吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class MyLinkedList {
public:
// --单链表--
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
} *head;
// --初始化--
MyLinkedList() {
// --哨兵节点--
head = new ListNode;
}
// --获取index位置的值,不存在返回-1--
int get(int index) {
ListNode *tmp = head->next;
while (index--) {
if (!tmp) return -1;
tmp = tmp->next;
}
if (!tmp) return -1;
return tmp->val;
}
// --加到开头--
void addAtHead(int val) {
ListNode *newNode = new ListNode(val);
newNode->next = head->next;
head->next = newNode;
}
// --加到结尾--
void addAtTail(int val) {
ListNode *newNode = new ListNode(val);
ListNode *tmp = head;
while (tmp->next) tmp = tmp->next;
tmp->next = newNode;
}
// --加到index位置前--
void addAtIndex(int index, int val) {
ListNode *newNode = new ListNode(val);
ListNode *tmp = head;
while (index-- && tmp) tmp = tmp->next;
if (index > 0 || !tmp) return;
newNode->next = tmp->next;
tmp->next = newNode;
}
// --删除index节点--
void deleteAtIndex(int index) {
ListNode *tmp = head;
// --目标为tmp->next
while (index-- && tmp) tmp = tmp->next;
if (index > 0 || !tmp || !tmp->next) return;
ListNode *need2Delete = tmp->next;
tmp->next = tmp->next->next;
delete need2Delete;
}
};

/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList* obj = new MyLinkedList();
* int param_1 = obj->get(index);
* obj->addAtHead(val);
* obj->addAtTail(val);
* obj->addAtIndex(index,val);
* obj->deleteAtIndex(index);
*/

206.反转链表

力扣题目链接

1、双指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) return head;
// --一次记录两个节点--
ListNode *slow = head;
ListNode *fast = head->next;
ListNode *tmp = nullptr;
// --第一个先指向空--
slow->next = nullptr;
while (fast) {
// --改为:后一个指向前一个--
tmp = fast->next;
fast->next = slow;
slow = fast;
fast = tmp;
}
return slow;
}
};
  • 时间复杂度:O(n)

2、递归法

24.两两交换链表中的节点

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (!head || !head->next) return head;
// --添加一个哨兵节点--
// --一次记录三个节点--
ListNode *head0 = new ListNode(0, head);
ListNode *pre = head0;
ListNode *key1 = head, *key2 = head->next;
while (1) {
// --改变结构--
pre->next = key2;
key1->next = key2->next;
key2->next = key1;
// --准备下一次操作--
pre = key1;
key1 = key1->next;
if (!key1) return head0->next;
key2 = key1->next;
if (!key2) return head0->next;
}
}
};
  • 时间复杂度:O(n)

19.删除链表的倒数第N个节点

力扣题目链接

1、循环两次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
// --计数--
int count(ListNode* head) {
int cnt = 0;
while (head) {
cnt++;
head = head->next;
}
return cnt;
}
ListNode* removeNthFromEnd(ListNode* head, int n) {
// --倒数化为正数--
n = count(head) - n + 1;
// --只有一个的话,n也只能为1了--
if (!head->next) {
delete head;
return nullptr;
}
// --增加一个哨兵节点--
ListNode *head0 = new ListNode(0, head);
ListNode *fast = head0, *slow = nullptr;
while (n--) {
slow = fast;
fast = fast->next;
}
slow->next = fast->next;
delete fast;
return head0->next;
}
};
  • 时间复杂度:O(2n)

2、双指针【进阶】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
// --增加一个哨兵节点--
ListNode *head0 = new ListNode(0, head);
ListNode *fast = head0, *slow = head0;
// --fast比slow块n个,fast都是有效节点,slow->next是最后要删除的节点--
// --fast先前进n次--
while (n--) fast = fast->next;
// --fast和slow一起前进,知道fast取到最后一个有效节点--
while (fast->next) {
fast = fast->next;
slow = slow->next;
}
// --删除slow->next--
ListNode *need2Delete = slow->next;
slow->next = slow->next->next;
delete need2Delete;
return head0->next;
}
};
  • 时间复杂度:O(n)

面试题 02.07. 链表相交

力扣题目链接

同:160. 相交链表 - 力扣(Leetcode)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
// --计数--
int count(ListNode *head) {
int cnt = 0;
while (head) {
cnt++;
head = head->next;
}
return cnt;
}
// --传入的值nA >= nB--
ListNode *findAnsNode(int nA, int nB, ListNode *headA, ListNode *headB) {
// --headA先前进nA - nB个--
for (int i = 0; i < nA - nB; i++) headA = headA->next;
if (headA == headB) return headA;
while (nB--) {
// --走到最后都没有相等--
if (!headA->next || !headB->next) return nullptr;
// --目标是->next--
if (headA->next == headB->next) return headA->next;
headA = headA->next;
headB = headB->next;
}
return nullptr;
}
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int nA = count(headA), nB = count(headB);
if (nA >= nB) return findAnsNode(nA, nB, headA, headB);
else return findAnsNode(nB, nA, headB, headA);
}
};
  • 时间复杂度:O(n + m)

  • 空间复杂度:O(1)

142.环形链表II

力扣题目链接

找到相遇点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
// --slow移动一步, fast移动两步--
slow = slow->next;
fast = fast->next->next;
// --相遇了--
if (slow == fast) {
// --x:起始点到环入口的距离--
// --y:环入口到相遇点的距离--
// --z:相遇点到环入口的距离--
// --2(x + y) = x + y + n(y + z)--
// --x = n(y + z) - y--
// --slow从起点开始,fast从相遇点开始--
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
// --出现了终点--
return nullptr;
}
};

三、哈希表

242.有效的字母异位词

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
bool isAnagram(string s, string t) {
vector<int> charSet(26, 0);
int ns = s.size(), nt = t.size();
for (int i = 0; i < ns; i++) {
charSet[s[i] - 'a']++;
}
for (int i = 0; i < nt; i++) {
charSet[t[i] - 'a']--;
}
for (int i = 0; i < 26; i++) {
if (charSet[i] != 0) return false;
}
return true;
}
};

349.两个数组的交集

力扣题目链接

1、哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> ans;
unordered_set<int> nums1_set(nums1.begin(), nums1.end());
for (int item : nums2) {
// --在nums1中,但是不重复出现--
if (nums1_set.find(item) != nums1_set.end()) {
ans.insert(item);
}
}
return vector<int>(ans.begin(), ans.end());
}
};

2、数组做哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> ans;
int record[1000] = {0}; // 初始化为0
int n1 = nums1.size(), n2 = nums2.size();
for (int i = 0; i < n1; i++) {
record[nums1[i]] = 1;
}
for (int i = 0; i < n2; i++) {
if (record[nums2[i]]) ans.insert(nums2[i]);
}
return vector<int>(ans.begin(), ans.end());;
}
};

202.快乐数

力扣题目链接

1、快慢指针 + 递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
// --计算位平方和--
int getSum(int n) {
int sum = 0;
while (n) {
sum += (n % 10) * (n % 10);
n /= 10;
}
return sum;
}
// --递归 + 快慢指针求解--
bool judge(int fast, int slow) {
// --fast计算两次,slow计算一次--
fast = getSum(getSum(fast));
slow = getSum(slow);
// --重复出现--
if (fast == 1) return true;
if (fast == slow) return false;
return judge(fast, slow);
}
bool isHappy(int n) {
return judge(n, n);
}
};

2、哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
// --计算位平方和--
int getSum(int n) {
int sum = 0;
while (n) {
sum += (n % 10) * (n % 10);
n /= 10;
}
return sum;
}
bool judge(int n, unordered_set<int>& cnt) {
if (n == 1) return true;
if (cnt.find(n) != cnt.end()) {
return false;
}
else {
cnt.insert(n);
}
n = getSum(n);
return judge(n, cnt);
}
bool isHappy(int n) {
// --哈希表(元素不重复)--
unordered_set<int> cnt;
return judge(n, cnt);
}
};

1.两数之和

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> record;
// --查找差是否在map中--
int n = nums.size();
for (int i = 0; i < n; i++) {
if (record.find(target - nums[i]) != record.end()) {
return {i, record.find(target - nums[i])->second};
}
// --不在则记到map中--
record.insert(pair<int, int>(nums[i], i));
}
return {};
}
};

454.四数相加II

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
int ans = 0;
int n1 = nums1.size(), n2 = nums2.size(), n3 = nums3.size(), n4 = nums4.size();
unordered_map<int, int> map;
for (int i : nums1) {
for (int j : nums2) {
map[i + j]++;
}
}
for (int k : nums3) {
for (int l : nums4) {
// --在map中--
if (map.find(0 - k - l) != map.end()) {
ans += map[0 - k - l];
}
}
}
return ans;
}
};

383.赎金信

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
vector<int> mCnt(26, 0); // 记录杂志字母出现次数
for (char i : magazine)
mCnt[i - 'a']++;
for (char i : ransomNote) {
mCnt[i - 'a']--;
// --单词不够了--
if (mCnt[i - 'a'] < 0) return false;
}
return true;
}
};

15.三数之和

力扣题目链接

18.四数之和

力扣题目链接

四、字符串

344.反转字符串

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
void reverseString(vector<char>& s) {
int left = 0, right = s.size() - 1;
while (left < right) {
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++; right--;
}
}
};

541.反转字符串II

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
// --修改了344.反转字符串的代码--
void reverseString(string& s, int left, int right) {
while (left < right) {
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++; right--;
}
}
string reverseStr(string s, int k) {
int n = s.size(); // 获取长度
int begin = 0; // 第几2k的起止位置
for (int i = 0; i < n; i += 2 * k) {
// --判断一下剩余字符--
int left = n - i;
if (left < k) {
reverseString(s, begin, n - 1);
break;
}
else if (left < 2 * k) {
reverseString(s, begin, begin + k - 1);
break;
}
// --开始翻转--
reverseString(s, begin, begin + k - 1);
begin += 2 * k;
}
return s;
}
};

剑指Offer 05.替换空格

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
string replaceSpace(string s) {
// --计算空格数--
int oldSize = s.size();
int cnt = 0;
for (int i = 0; i < oldSize; i++) {
if (s[i] == ' ') cnt++;
}
// --扩大数组,加上所有空格的大小(本来就占用一个了)--
s.resize(oldSize + cnt *2);
int newSize = s.size();
// --slow遍历,fast指向下一个存放的位置--
int slow = oldSize - 1, fast = newSize - 1;
while (slow < fast) {
if (s[slow] == ' ') {
s[fast--] = '0';
s[fast--] = '2';
s[fast--] = '%';
slow--;
}
else s[fast--] = s[slow--];
}
return s;
}
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

151.翻转字符串里的单词

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
// --修改了344.反转字符串的代码--
void reverseString(string& s, int left, int right) {
while (left < right) {
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++; right--;
}
}
// --处理多余空格--
void processSpaces(string& s) {
int slow = 0;
int n = s.size();
int flag = 0; // 1;遇到过单词
for (int fast = 0; fast < n; fast++) {
if (s[fast] != ' ') {
flag = 1;
s[slow++] = s[fast];
}
else {
// --前面有单词,加一个空格--
if (flag) s[slow++] = ' ';
flag = 0;
}
}
// --最后有一个空格,或者没有--
if (s[slow - 1] == ' ') s.resize(slow - 1);
else s.resize(slow);
}
string reverseWords(string s) {
// --首先将多余空格处理完--
processSpaces(s);
// --整体翻转--
reverseString(s, 0, s.size() - 1);
// --每个单词进行翻转--
int begin = 0, end = 0;
int n = s.size();
while (end < n) {
// --区间为[begin, end - 1]--
if (s[end] == ' ') {
reverseString(s, begin, end - 1);
begin = end + 1;
}
end++;
}
// --最后一个单词没被翻转,加上--
reverseString(s, begin, end - 1);
return s;
}
};

剑指Offer58-II.左旋转字符串

力扣题目链接

不开辟新的空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
// --修改了344.反转字符串的代码--
void reverseString(string& s, int left, int right) {
while (left < right) {
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++; right--;
}
}
string reverseLeftWords(string s, int n) {
// --目的:0 ~ k移动到k + 1 ~ n - 1(这里k = n, n = size)---
// --先各自翻转,再整体翻转就是答案了--
reverseString(s, 0, n - 1);
reverseString(s, n, s.size() - 1);
reverseString(s, 0, s.size() - 1);
return s;
}
};

28.实现 strStr()

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
// --获取模式串s的next数组--
vector<int> getNext(string s) {
int n = s.size();
vector<int> next(n, 0); // 大小和初值
int j = -1;
next[0] = j;
// --j + 1指向前缀的末尾,i指向后缀的末尾--
for (int i = 1; i < n; i++) {
// --不匹配,j回退--
while (j >= 0 && s[j + 1] != s[i]) {
j = next[j];
}
// --匹配,同时前进--
if (s[j + 1] == s[i]) j++;
// --记录next数组--
next[i] = j;
}
return next;
}
int strStr(string haystack, string needle) {
// --对于本题可以不写--
if (needle.size() == 0) return 0;
vector<int> next = getNext(needle);
int n = haystack.size(), m = needle.size();
int j = -1;
for (int i = 0; i < n; i++) {
// --不匹配,j回退--
while (j >= 0 && needle[j + 1] != haystack[i]) {
j = next[j];
}
// --匹配,前进--
if (needle[j + 1] == haystack[i]) j++;
// --完全匹配,结束--
if (j + 1 == m) {
return i - needle.size() + 1;
}
}
return -1;
}
};

459.重复的子字符串

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
// --来自28. 实现 strStr()--
vector<int> getNext(string s) {
int n = s.size();
vector<int> next(n, 0); // 大小和初值
int j = -1;
next[0] = j;
// --j + 1指向前缀的末尾,i指向后缀的末尾--
for (int i = 1; i < n; i++) {
// --不匹配,j回退--
while (j >= 0 && s[j + 1] != s[i]) {
j = next[j];
}
// --匹配,同时前进--
if (s[j + 1] == s[i]) j++;
// --记录next数组--
next[i] = j;
}
return next;
}
bool repeatedSubstringPattern(string s) {
if (s.size() == 0) return false;
vector<int> next = getNext(s);
if (next[next.size() - 1] != -1
&& s.size() % (next.size() - next[next.size() - 1] - 1) == 0)
return true;
return false;
}
};

五、双指针法(同上)

27.移除元素

力扣题目链接

344.反转字符串

力扣题目链接

剑指Offer 05.替换空格

力扣题目链接

151.翻转字符串里的单词

力扣题目链接

206.反转链表

力扣题目链接

24. 两两交换链表中的节点

力扣题目链接

19.删除链表的倒数第N个节点

力扣题目链接

面试题 02.07. 链表相交

力扣题目链接

同:160. 相交链表 - 力扣(Leetcode)

142.环形链表II

力扣题目链接

15.三数之和

力扣题目链接

18.四数之和

力扣题目链接

六、栈与队列

232.用栈实现队列

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class MyQueue {
public:
// -- 输入栈、输出栈 --
stack<int> stackIn;
stack<int> stackOut;
MyQueue() { }
void push(int x) {
stackIn.push(x);
}
int pop() {
// -- 输出栈为空,将输入栈的元素全部取出,放入输出栈 --
if (stackOut.empty()) {
while (!stackIn.empty()) {
stackOut.push(stackIn.top());
stackIn.pop();
}
}
// -- 输出栈为空,输入栈为空,报错 --
if (stackOut.empty()) {
printf("当前没有元素\n");
return -1;
}
// -- 输出栈不为空,直接输出 --
int res = stackOut.top();
stackOut.pop();
return res;
}

int peek() {
// --使用了自身的函数,但是pop删除了元素,需要恢复--
int res = this->pop();
stackOut.push(res);
return res;
}

bool empty() {
if (stackOut.empty() && stackIn.empty()) return true;
return false;
}
};

/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/

225.用队列实现栈

力扣题目链接

1、两个队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class MyStack {
public:
// --q1作为输入输出栈,q2作为辅助备份栈--
queue<int> q1;
queue<int> q2;
MyStack() {}

void push(int x) {
q1.push(x);
}

int pop() {
// --q1为空,q2为空,报错--
if (this->empty()) printf("当前没有元素\n");
// --q1所有元素放到q2,除了最后一个元素--
int size = q1.size() - 1;
while (size--) {
q2.push(q1.front());
q1.pop();
}
// --最后一个元素就是栈顶--
int res = q1.front();
q1.pop();
// --q1为空,q2不为空,q2变换为q1,q1变换为q2--
if (q1.empty()) swap(q1, q2);
return res;
}

int top() {
// --使用了自身的函数,但是pop删除了元素,需要恢复--
int res = this->pop();
q1.push(res);
return res;
}

bool empty() {
if (q1.empty() && q2.empty()) return true;
return false;
}
};

/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/

2、一个队列(优化)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class MyStack {
public:
queue<int> q;
MyStack() { }

void push(int x) {
q.push(x);
}

int pop() {
// --把前n个重新入队,则最后一个变为第一个,删除即可--
int res = q.back();
int t = q.size() - 1;
while (t--) {
q.push(q.front());
q.pop();
}
q.pop();
return res;
}

int top() {
// --调用自己的pop,将弹出的添加回去--
int res = this->pop();
q.push(res);
return res;
}

bool empty() {
if (q.empty()) return true;
return false;
}
};

/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/

20.有效的括号

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
bool isValid(string s) {
stack<char> st;
int n = s.size();
for (int i = 0; i < n; i++ ) {
// --放入对应的括号,匹配问题变成了相等问题--
if (s[i] == '(') st.push(')');
else if (s[i] == '[') st.push(']');
else if (s[i] == '{') st.push('}');
else {
// --1、栈为空--
if (st.empty()) return false;
// --2、匹配上--
else if (st.top() == s[i]) st.pop();
// --3、不匹配--
else return false;
}
}
// --4、执行完了,栈不为空--
return st.empty();
}
};

1047.删除字符串中的所有相邻重复项

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
string removeDuplicates(string s) {
int slow = 0; // 指向栈顶的下一个位置
for (int i = 0; i < s.size(); i++) {
// --1、栈为空--
if (slow == 0) {
s[slow++] = s[i];
}
// --2、不相同--
else if (s[slow - 1] != s[i]) {
s[slow++] = s[i];
}
// --3、相同--
else {
slow--;
}
}
s.resize(slow);
return s;
}
};

150.逆波兰表达式求值

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
// --转为整数--
int str2int(const string str) {
int res = 0;
int flag = 0; // 1:负数
for (char i : str) {
if (i == '-') {
flag = 1;
continue;
}
res = res * 10 + i - '0';
}
return flag ? 0 - res : res;
}
int evalRPN(vector<string>& tokens) {
// --数字栈, 力扣修改了后台测试数据,需要用longlong--
stack<long long> st;
for (string i : tokens) {
// --是数字, 考虑负数--
if (i[0] >= '0' && i[0] <= '9' || i[0] == '-' && i.size() > 1) {
st.push(str2int(i));
printf("%d压入栈\n", str2int(i));
}
// --是符号--
else {
// --弹出两个操作数,计算--
int tmp = 0;
int key2 = st.top();
st.pop();
int key1 = st.top();
st.pop();
if (i[0] == '+') {
tmp = key1 + key2;
}
else if (i[0] == '-') {
tmp = key1 - key2;
}
else if (i[0] == '*') {
tmp = key1 * key2;
}
else if (i[0] == '/') {
tmp = key1 / key2;
}
// --压入计算结果--
st.push(tmp);
printf("%d %c %d = %d\n", key1, i[0], key2, tmp);
}
}
return st.top();
}
};

七、二叉树

递归遍历/迭代遍历

144.二叉树的前序遍历

力扣题目链接

1、递归遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void traverse(TreeNode *node, vector<int>& ans) {
if (node == nullptr) return;
ans.push_back(node->val);
traverse(node->left, ans);
traverse(node->right, ans);
return;
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
traverse(root, ans);
return ans;
}
};

2、迭代遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode *> st;
st.push(root);
while (!st.empty()) {
TreeNode *tmp = st.top();
st.pop();
if (tmp == nullptr) continue;
ans.push_back(tmp->val);
st.push(tmp->right);
st.push(tmp->left);
}
return ans;
}
};

145.二叉树的后序遍历

力扣题目链接

1、递归遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void traverse(TreeNode *node, vector<int>& ans) {
if (node == nullptr) return;
traverse(node->left, ans);
traverse(node->right, ans);
ans.push_back(node->val);
return;
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
traverse(root, ans);
return ans;
}
};

2、迭代遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode *> st;
st.push(root);
// --修改前序,将顺序变为中右左,最后再翻转就是答案--
while (!st.empty()) {
TreeNode *tmp = st.top();
st.pop();
if (tmp == nullptr) continue;
ans.push_back(tmp->val);
st.push(tmp->left);
st.push(tmp->right);
}
reverse(ans.begin(), ans.end());
return ans;
}
};

94.二叉树的中序遍历

力扣题目链接

1、递归遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void traverse(TreeNode *node, vector<int>& ans) {
if (node == nullptr) return;
traverse(node->left, ans);
ans.push_back(node->val);
traverse(node->right, ans);
return;
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
traverse(root, ans);
return ans;
}
};

2、迭代遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode *> st;
while (root || !st.empty()) {
if (root != nullptr) {
st.push(root);
// printf("%d进栈\n", root->val);
root = root->left;
}
else {
root = st.top();
ans.push_back(root->val);
st.pop();
// printf("%d出栈\n", root->val);
root = root->right;
}
}
return ans;
}
};

589.N 叉树的前序遍历

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;

Node() {}

Node(int _val) {
val = _val;
}

Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/

class Solution {
public:
vector<int> ans;
vector<int> preorder(Node* root) {
if (root == nullptr) return ans;
ans.push_back(root->val); // 前
for (int i = 0; i < root->children.size(); i++)
preorder(root->children[i]);
return ans;
}
};

590.N 叉树的后序遍历

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;

Node() {}

Node(int _val) {
val = _val;
}

Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/

class Solution {
public:
vector<int> ans;
vector<int> postorder(Node* root) {
if (root == nullptr) return ans;
for (int i = 0; i < root->children.size(); i++)
preorder(root->children[i]);
ans.push_back(root->val); // 后
return ans;
}
};

层序遍历

102.二叉树的层序遍历

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (!root) return ans;
queue<TreeNode *> que;
que.push(root);
while (!que.empty()) {
int curSize = que.size(); // 当前层有多少个
vector<int> curAns; // 记录当前层答案
for (int i = 0; i < curSize; i++) {
TreeNode *tmp = que.front();
curAns.push_back(tmp->val);
que.pop();
if (tmp->left) que.push(tmp->left);
if (tmp->right) que.push(tmp->right);
}
ans.push_back(curAns);
}
return ans;
}
};

107.二叉树的层序遍历 II

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> ans;
if (!root) return ans;
queue<TreeNode *> que;
que.push(root);
while (!que.empty()) {
int curSize = que.size(); // 当前层有多少个
vector<int> curAns; // 记录当前层答案
for (int i = 0; i < curSize; i++) {
TreeNode *tmp = que.front();
curAns.push_back(tmp->val);
que.pop();
if (tmp->left) que.push(tmp->left);
if (tmp->right) que.push(tmp->right);
}
ans.push_back(curAns);
}
reverse(ans.begin(), ans.end()); // 翻转就行了
return ans;
}
};

199. 二叉树的右视图

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> ans;
if (root == nullptr) return ans;
queue<TreeNode *> que;
que.push(root);
while (!que.empty()) {
int n = que.size() - 1;
// --把每一层的最后一个记录下来后弹出,其他弹出即可--
while (n--) {
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
que.pop();
}
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
ans.push_back(que.front()->val);
que.pop();
}
return ans;
}
};

637.二叉树的层平均值

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
vector<double> ans;
if (!root) return ans;
queue<TreeNode *> que;
que.push(root);
while (!que.empty()) {
double curSum = 0; // 当前层数的和
int size = que.size();
for (int i = 0; i < size; i++) {
curSum += que.front()->val;
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
que.pop();
}
ans.push_back(curSum / size); // 写入平均值
}
return ans;
}
};

429.N叉树的层序遍历

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;

Node() {}

Node(int _val) {
val = _val;
}

Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/

class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> ans;
if (!root) return ans;
queue<Node *> que;
que.push(root);
while (!que.empty()) {
int curSize = que.size(); // 当前层有多少个
vector<int> curAns; // 记录当前层答案
for (int i = 0; i < curSize; i++) {
Node *tmp = que.front();
curAns.push_back(tmp->val);
que.pop();
// --压入孩子节点--
for (Node* j : tmp->children)
if (j) que.push(j);
}
ans.push_back(curAns);
}
return ans;
}
};

515.在每个树行中找最大值

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
vector<int> ans;
if (!root) return ans;
queue<TreeNode *> que;
que.push(root);
while (!que.empty()) {
int curMax = INT_MIN; // 当前层的最大值
int size = que.size();
for (int i = 0; i < size; i++) {
curMax = curMax < que.front()->val ? que.front()->val : curMax;
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
que.pop();
}
ans.push_back(curMax); // 写入答案
}
return ans;
}
};

116.填充每个节点的下一个右侧节点指针

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;

Node() : val(0), left(NULL), right(NULL), next(NULL) {}

Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
Node* connect(Node* root) {
if (!root) return root;
queue<Node *> que;
que.push(root);
while (!que.empty()) {
int curSize = que.size(); // 当前层有多少个
for (int i = 0; i < curSize; i++) {
Node *tmp = que.front();
que.pop();
// --如果是最后一个--
if (i == curSize - 1) tmp->next = nullptr;
else tmp->next = que.front();
if (tmp->left) que.push(tmp->left);
if (tmp->right) que.push(tmp->right);
}
}
return root;
}
};

117.填充每个节点的下一个右侧节点指针II

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;

Node() : val(0), left(NULL), right(NULL), next(NULL) {}

Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
Node* connect(Node* root) {
if (!root) return root;
queue<Node *> que;
que.push(root);
while (!que.empty()) {
int curSize = que.size(); // 当前层有多少个
for (int i = 0; i < curSize; i++) {
Node *tmp = que.front();
que.pop();
// --如果是最后一个--
if (i == curSize - 1) tmp->next = nullptr;
else tmp->next = que.front();
if (tmp->left) que.push(tmp->left);
if (tmp->right) que.push(tmp->right);
}
}
return root;
}
};

104.二叉树的最大深度

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
int ans = 0;
if (!root) return ans;
queue<TreeNode *> que;
que.push(root);
while (!que.empty()) {
ans++;
int curSize = que.size(); // 当前层有多少个
for (int i = 0; i < curSize; i++) {
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
que.pop();
}
}
return ans;
}
};

111.二叉树的最小深度

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int minDepth(TreeNode* root) {
int ans = 0;
if (!root) return ans;
queue<TreeNode *> que;
que.push(root);
while (!que.empty()) {
int curSize = que.size(); // 当前层有多少个
ans++;
for (int i = 0; i < curSize; i++) {
// --是否是叶子节点,是的话后面都没必要执行了--
if (!que.front()->left && !que.front()->right) return ans;
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
que.pop();
}
}
return ans;
}
};

226.翻转二叉树

力扣题目链接

1、递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) return root;
swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
};

2、迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) return root;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode *tmp = st.top();
swap(tmp->left, tmp->right);
st.pop();
if (tmp->right) st.push(tmp->right);
if (tmp->left) st.push(tmp->left);
}
return root;
}
};

100.相同的树

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
// --1. 子树都为空--
if (!p && !q) return true;
// --2. 子树有一个不为空--
if (p && !q || !p && q) return false;
// --3. 子树都不为空--
if (p->val == q->val // 自己是否相等
&& isSameTree(p->left, q->left) // p左子树和q左子树是否相等
&& isSameTree(p->right, q->right)) // p右子树和q右子树是否相等
return true;
return false;
}
};

101.对称二叉树

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool preOrdertraverse(TreeNode *t1, TreeNode *t2) {
// --1. 子树都为空--
if (!t1 && !t2) return true;
// --2. 子树有一个不为空--
if (t1 && !t2 || !t1 && t2) return false;
// --3. 子树都不为空--
if (t1->val == t2->val // 自己是否相等
&& preOrdertraverse(t1->left, t2->right) // t1左子树和t2右子树是否相等
&& preOrdertraverse(t1->right, t2->left)) // t1右子树和t2左子树是否相等
return true;
return false;
}
bool isSymmetric(TreeNode* root) {
if (!root) return true;
return preOrdertraverse(root->left, root->right);
}
};

572.另一棵树的子树

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// --来自 100.相同的树 --
bool isSameTree(TreeNode* p, TreeNode* q) {
// --1. 子树都为空--
if (!p && !q) return true;
// --2. 子树有一个不为空--
if (p && !q || !p && q) return false;
// --3. 子树都不为空--
if (p->val == q->val // 自己是否相等
&& isSameTree(p->left, q->left) // p左子树和q左子树是否相等
&& isSameTree(p->right, q->right)) // p右子树和q右子树是否相等
return true;
return false;
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if (!root) return false;
return isSameTree(root, subRoot)
|| isSubtree(root->left, subRoot)
|| isSubtree(root->right, subRoot);
}
};

559.n叉树的最大深度

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;

Node() {}

Node(int _val) {
val = _val;
}

Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/

class Solution {
public:
int maxDepth(Node* root) {
int ans = 0;
if (!root) return ans;
queue<Node *> que;
que.push(root);
while (!que.empty()) {
ans++;
int curSize = que.size(); // 当前层有多少个
for (int i = 0; i < curSize; i++) {
for (Node* j : que.front()->children)
if (j) que.push(j);
que.pop();
}
}
return ans;
}
};

222.完全二叉树的节点个数

力扣题目链接

1、当做普通二叉树遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int countNodes(TreeNode* root) {
int ans = 0;
if (!root) return ans;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
ans++;
TreeNode *tmp = st.top(); // 中
st.pop();
if (tmp->right) st.push(tmp->right); // 右
if (tmp->left) st.push(tmp->left); // 左
}
return ans;
}
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

2、完全二叉树

完全二叉树只有两种情况,情况一:就是满二叉树,情况二:最后一层叶子节点没有满。
对于情况一,可以直接用 2^树深度 - 1 来计算,注意这里根节点深度为1。
对于情况二,分别递归左孩子,和右孩子,递归到某一深度一定会有左孩子或者右孩子为满二叉树,然后依然可以按照情况1来计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int countNodes(TreeNode* root) {
if (!root) return 0;
TreeNode *left = root->left;
TreeNode *right = root->right;
int lenLeft = 0, lenRight = 0;
// --统计左边深度--
while (left) {
lenLeft++;
left = left->left;
}
// --统计右边深度--
while (left) {
lenRight++;
right = right->right;
}
// --左边深度 等于 右边深度,说明这里完全二叉树是满二叉树--
if (lenLeft == lenRight) return (2 << lenLeft) - 1; // 右移相当于*2
return 1 + countNodes(root->left) + countNodes(root->right);
}
};
  • 时间复杂度:O(log n × log n)
  • 空间复杂度:O(log n)

110.平衡二叉树

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// --返回深度--
int postOrderTravese(TreeNode *t, int depth) {
if (!t) return depth - 1;
int lenLeft = postOrderTravese(t->left, depth + 1);
int lenRight = postOrderTravese(t->right, depth + 1);
return abs(lenLeft - lenRight) > 1 ? -1 : max(lenLeft, lenRight);
}
bool isBalanced(TreeNode* root) {
if (!root) return true;
if (postOrderTravese(root, 1) == -1) return false;
return true;
}
};

257. 二叉树的所有路径

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void postOrderTraverse(TreeNode *t, string s, vector<string>& ans) {
// --是叶子节点--
if (!t->left && !t->right) ans.push_back(s);
else {
// --左子树不为空--
if (t->left) postOrderTraverse(t->left, s + "->" + to_string(t->left->val), ans);
// --右子树不为空--
if (t->right) postOrderTraverse(t->right, s + "->" + to_string(t->right->val), ans);
}
return;
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> ans;
if (!root) return ans;
postOrderTraverse(root, to_string(root->val), ans);
return ans;
}
};

404.左叶子之和

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int sumOfLeftLeaves(TreeNode* root) {
if (!root) return 0;
int ans = 0;
queue<TreeNode *> que;
que.push(root);
while (!que.empty()) {
int size = que.size();
while (size--) {
if (que.front()->left) {
que.push(que.front()->left);
// --是左子树,判断是否是叶子结点--
if (!que.front()->left->left && !que.front()->left->right)
ans += que.front()->left->val;
}
if (que.front()->right) que.push(que.front()->right);
que.pop();
}
}
return ans;
}
};

513.找树左下角的值

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// @lc code=start
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
if (!root) return 0;
int ans = 0;
queue<TreeNode *> que;
que.push(root);
while (!que.empty()) {
int size = que.size();
// --更新为这一层的第一个即可--
ans = que.front()->val;
while (size--) {
if (que.front()->left) que.push(que.front()->left);
if (que.front()->right) que.push(que.front()->right);
que.pop();
}
}
return ans;
}
};

112.路径总和

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool traverse(TreeNode *t, int targetSum, int curSum) {
if (!t) return false;
curSum += t->val;
// --是叶子节点并且,curSum 为目标值
if (curSum == targetSum && !t->left && !t->right)
return true;
return traverse(t->left, targetSum, curSum)
|| traverse(t->right, targetSum, curSum);
}
bool hasPathSum(TreeNode* root, int targetSum) {
return traverse(root, targetSum, 0);
}
};

106.从中序与后序遍历序列构造二叉树

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// --返回key的索引--
int findRoot (vector<int>& inorder, int key, int inbegin, int inend) {
for (int i = inbegin; i <= inend; i++) {
if (inorder[i] == key) return i;
}
return -1;
}
TreeNode* preOrder(vector<int>& inorder, int inbegin, int inend,
vector<int>& postorder, int postbegin, int postend) {
// printf("[%d, %d], [%d, %d]\n", inbegin, inend, postbegin, postend);
// --没有节点了--
if (inbegin > inend) return nullptr;
// --在中根序中找到根节点--
int inRoot = findRoot(inorder, postorder[postend], inbegin, inend);
// --构造节点,改变区间接着递归--
return new TreeNode(postorder[postend], // 根
preOrder(inorder, inbegin, inRoot - 1, postorder, postbegin, postbegin + (inRoot - 1 - inbegin)), // 左子树
preOrder(inorder, inRoot + 1, inend, postorder, postend - 1 - (inend - inRoot - 1) ,postend - 1)); // 右子树
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return preOrder(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
}
};

654.最大二叉树

力扣题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// --返回最大值的索引--
int findRoot (vector<int>& nums, int begin, int end) {
int maxVal = INT_MIN, index = -1;
for (int i = begin; i <= end; i++)
if (maxVal < nums[i]) {
maxVal = nums[i];
index = i;
}
return index;
}
TreeNode* construct(vector<int>& nums, int begin, int end) {
if (begin > end) return nullptr;
int indexRoot = findRoot(nums, begin, end);
return new TreeNode(nums[indexRoot], // 根
construct(nums, begin, indexRoot - 1), // 左子树
construct(nums, indexRoot + 1, end)); // 右子树
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return construct(nums, 0, nums.size() - 1);
}
};

617.合并二叉树

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
// --1、两个都为空--
if (!root1 && !root2) return nullptr;
// --2、有一个为空--
if (!root1 && root2) return root2;
if (root1 && !root2) return root1;
// --3、都不为空--
root1->val += root2->val;
root1->left = mergeTrees(root1->left, root2->left);
root1->right = mergeTrees(root1->right, root2->right);
return root1;
}
};

700.二叉搜索树中的搜索

力扣题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if (!root) return nullptr;
// --本节点是--
if (root->val == val) return root;
// 递归
TreeNode *left = searchBST(root->left, val);
if (left) return left;
return searchBST(root->right, val);
}
};

98.验证二叉搜索树

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void inorder(TreeNode* t, vector<int>& res) {
if (!t) return;
inorder(t->left, res);
res.push_back(t->val);
inorder(t->right, res);
return;
}
bool isValidBST(TreeNode* root) {
// --将中根序放入数组中,检查是否有序即可--
vector<int> res;
inorder(root, res);
for (int i = 1; i < res.size(); i++)
if (res[i - 1] >= res[i]) return false;
return true;
}
};

530.二叉搜索树的最小绝对差

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void inorder(TreeNode* t, vector<int>& res) {
if (!t) return;
inorder(t->left, res);
res.push_back(t->val);
inorder(t->right, res);
return;
}
int getMinimumDifference(TreeNode* root) {
// --将中根序放入数组中,计算最小差值即可--
vector<int> res;
inorder(root, res);
int minDiff = INT_MAX;
for (int i = 1; i < res.size(); i++) {
int tmp = res[i] - res[i - 1];
minDiff = minDiff > tmp ? tmp : minDiff;
}
return minDiff;
}
};

501.二叉搜索树中的众数

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> majority; // 记录当前找到的众数
int curMSize = 0; // 记录当前找到的众数,它有多少个
int cnt = 0; // 记录当前重复元素
int pre = INT_MIN; // 上一个元素
void inOrderTraverse(TreeNode* root) {
if (!root) return;
inOrderTraverse(root->left);
// --与上一个元素相同,意味着重复了--
if (pre == root->val) cnt++;
else cnt = 1;
pre = root->val;
printf("%d %d\n", curMSize, cnt);
if (curMSize == cnt) majority.push_back(root->val);
else if (curMSize < cnt) {
// --将所有元素清空,将这个众数放入--
vector<int>().swap(majority);
majority.push_back(root->val);
curMSize = cnt;
}
inOrderTraverse(root->right);
}
vector<int> findMode(TreeNode* root) {
inOrderTraverse(root);
return majority;
}
};

236. 二叉树的最近公共祖先

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == p || root == q || root == NULL) return root;
TreeNode *left = lowestCommonAncestor(root->left, p, q);
TreeNode *right = lowestCommonAncestor(root->right, p, q);
if (left && !right) return left;
if (!left && right) return right;
if (left && right) return root;
return nullptr;
}
};

701.二叉搜索树中的插入操作

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (!root) return root = new TreeNode(val);
// --看左子树--
if (val < root->val) {
if (!root->left)
root->left = new TreeNode(val);
else insertIntoBST(root->left, val);
}
// --看右子树--
if (val > root->val) {
if (!root->right)
root->right = new TreeNode(val);
else insertIntoBST(root->right, val);
}
return root;
}
};

450.删除二叉搜索树中的节点

力扣题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) return root;
// --找到要删除的节点--
if (root->val == key) {
TreeNode *need2delete = root;
// --1、左右孩子都为空--
if (!root->left && !root->right) root = nullptr;
// --2、左孩子为空--
else if (!root->left && root->right) root = root->right;
// --3、右孩子为空--
else if (root->left && !root->right) root = root->left;
// --4、左右孩子都不为空--
else if (root->left && root->right) {
// --左子树放到右子树的左下角叶节点的左孩子上--
TreeNode *tmp = root->right;
while (tmp->left) tmp = tmp->left;
tmp->left = root->left;
root = root->right;
}
delete need2delete;
}
// --没找到--
else {
if (root->val > key) root->left = deleteNode(root->left, key);
if (root->val < key) root->right = deleteNode(root->right, key);
}
return root;
}
};

八、图论

797.所有可能的路径

797. 所有可能的路径 - 力扣(LeetCode)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
// -- 表结点 --
struct ArcNode {
int adjvex; // 邻接顶点
ArcNode *nextarc;
ArcNode() : adjvex(0), nextarc(NULL) {}
};
// -- 头结点 --
struct VNode {
ArcNode *nextarc;
VNode() : nextarc(NULL) {}
};
// -- 深搜 --
vector<vector<int>> ans;
void dfs(vector<int> &path, vector<VNode> vnode, int begin, int target) {
for (ArcNode *p = vnode[begin].nextarc; p; p = p->nextarc) {
path.push_back(p->adjvex);
if (p->adjvex == target) { // 找到了
vector<int> copypath;
copypath.assign(path.begin(), path.end());
ans.push_back(copypath);
path.pop_back(); // 回退
continue; // 这条路没必要往下了
}
dfs(path, vnode, p->adjvex, target); // 一直往下
path.pop_back(); // 回退
}
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
vector<VNode> vnode(graph.size());
// -- 构造邻接表 --
for (int i = 0; i < graph.size(); i++) {
for (int k : graph[i]) {
ArcNode *tmp = new(ArcNode);
tmp->adjvex = k;
tmp->nextarc = vnode[i].nextarc;
vnode[i].nextarc = tmp;
}
}
vector<int> path;
path.push_back(0); // 第一个位置是0
dfs(path, vnode, 0, graph.size()-1);
return ans;
}
};

200. 岛屿数量

200. 岛屿数量 - 力扣(LeetCode)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
int directionX[4] = {-1, 0, 1, 0};
int directionY[4] = {0, -1, 0, 1};
// 赋值并检查越界情况
bool check (int &i, int &j, int x, int y, int m, int n) {
int tmpi = i + x, tmpj = j + y;
if (tmpi <= -1 || tmpj <= -1
|| tmpi >= m || tmpj >= n) return false; // 越界
i = tmpi;
j = tmpj;
return true;
}
// -- 从i, j开始 --
void dfs(vector<vector<char>> &grid, vector<vector<int>>& visited, int i, int j, int m, int n) {
visited[i][j] = 1; // 标记已经访问
for (int k = 0; k < 4; k++) {
int x = directionX[k];
int y = directionY[k];
int tmpi = i, tmpj = j;
if (check(tmpi, tmpj, x, y, m, n) == false) continue; // 越界跳过
if (visited[tmpi][tmpj] == 0 && grid[tmpi][tmpj] == '1') {// 再在附近找一个可以过去的点,但是没去过的点
dfs(grid,visited , tmpi, tmpj, m, n);
}
}
}
int numIslands(vector<vector<char>>& grid) {
// -- 用类似找连通分量的方法 --
int ans = 0;
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> visited(m, vector<int>(n, 0)); // 标记结点是否访问过
for (int i = 0; i < m; i++) {
for (int j = 0; j < n ; j++) {
if (visited[i][j] == 0 && grid[i][j] == '1') {
ans++; // 一次dfs一个岛屿
dfs(grid, visited, i, j, m, n);
}
}
}
return ans;
}
};