---
tags: 刷題
---
# Leetcode learning use C++
<h1>數組</h1>
**1. Two Sum**
```cpp=
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> indices;
for(int i=0; i<nums.size(); i++) indices[nums[i]] = i;
for(int i=0; i<nums.size(); i++){
int left = target - nums[i];
if (indices.count(left) && indices[left]!=i) return {i, indices[left]};
}
return {};
}
};
```
```cpp=
// 使用 std::unordered_map
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
std::unordered_map <int,int> map;
for(int i = 0; i < nums.size(); i++) {
auto iter = map.find(target - nums[i]);
if(iter != map.end()) return {iter->second, i
map.insert({nums[i], i});
}
return {};
}
};
```
**35. Search Insert Position**
```cpp=
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0;
int right = nums.size()-1;
while(left <= right){
int mid = (left+right)/2;
if(target < nums[mid]){
right = mid-1;
}else if(target > nums[mid]){
left = mid+1;
}else return mid;
}
return right+1;
}
};
```
**27. Remove Element**
```cpp=
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slowPointer = 0;
for(int fastPointer = 0;fastPointer<nums.size();fastPointer++){
if(nums[fastPointer]!=val){
nums[slowPointer++] = nums[fastPointer];
}
}
return slowPointer;
}
};
```
```cpp=
//法二
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int leftIndex = 0;
int rightIndex = nums.size() -1 ;
while(leftIndex <= rightIndex){
while(leftIndex <= rightIndex && nums[leftIndex] != val){
leftIndex++;
}
while(leftIndex <= rightIndex && nums[rightIndex] == val){
rightIndex--;
}
if(leftIndex < rightIndex){
nums[leftIndex] = nums[rightIndex];
leftIndex++;
rightIndex--;
//nums[leftIndex++] = nums[rightIndex--];
}
}
return leftIndex;
}
};
```
**15. 3Sum**
```cpp=
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for(int i=0; i<nums.size(); i++){
int left = i+1;
int right = nums.size()-1;
if(nums[i]>0) return result;
if(i>0 && nums[i]==nums[i-1]) continue;
while(right>left){
if(nums[i]+nums[left]+nums[right] > 0) right--;
else if(nums[i]+nums[left]+nums[right] < 0) left++;
else{
result.push_back(vector<int>{nums[i], nums[left], nums[right]});
while(right > left && nums[left]==nums[left+1])left++;
while(right > left && nums[right]==nums[right-1])right--;
left++;
right--;
}
}
}
return result;
}
};
```
**209. Minimum Size Subarray Sum**
```cpp=
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int result = INT32_MAX;
int i = 0;
int sum = 0;
for(int j = 0; j < nums.size(); j++){
sum += nums[j];
while(sum >= target){
result = result < j-i+1 ? result:j-i+1;
sum -= nums[i++];
}
}
return result == INT32_MAX ? 0 : result;
}
};
```
**59. Spiral Matrix II**
```cpp=
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n, vector<int>(n, 0));
int startY = 0;
int startX = 0;
int offset = 1;
int round = n/2;
int count = 1;
int mid = n/2;
while(round--){
int j = startY;
int i = startX;
for(j = startY; j < startY + n - offset; j++) res[startX][j] = count++;
for(i = startX; i < startX + n - offset; i++) res[i][startY + n - offset] = count++;
for(; j > startY; j--) res[startY + n - offset][j] = count++;
for(; i> startY; i--) res[i][startX] = count++;
startY++;
startX++;
offset += 2;
}
if (n % 2) res[mid][mid] = count;
return res;
}
};
```
<h1>鍊錶</h1>
**203. Remove Linked List Elements**
<法一>
```cpp=
/**
* 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) {
while(head != NULL && head->val == val){
ListNode* tmp = head;
head = head->next;
delete tmp;
}
ListNode* cur = head;
while(cur != NULL && cur->next != NULL){
if(cur->next->val == val){
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
}else{
cur = cur->next;
}
}
return head;
}
};
```
<法二 虛擬頭結點> good
```cpp=
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummyNode = new ListNode(0);
dummyNode->next = head;
ListNode* cur = dummyNode;
while(cur->next != NULL){
if(cur->next->val == val){
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
}else{
cur = cur->next;
}
}
return dummyNode->next;
}
};
```
**707. Design Linked List**
```cpp=
class MyLinkedList {
public:
struct LinkedNode{
int val;
LinkedNode* next;
LinkedNode(int val):val(val), next(nullptr){}
};
MyLinkedList() {
_dummyNode = new LinkedNode(0);
_size = 0;
}
int get(int index) {
if(index+1 > _size || index < 0) return-1;
LinkedNode* cur = _dummyNode->next;
while(index--) cur = cur->next;
return cur->val;
}
void addAtHead(int val) {
LinkedNode* newhead = new LinkedNode(val);
newhead->next = _dummyNode->next;
_dummyNode->next = newhead;
_size++;
}
void addAtTail(int val) {
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = _dummyNode;
while(cur->next != nullptr) cur = cur->next;
cur->next = newNode;
_size++;
}
void addAtIndex(int index, int val) {
if(index > _size) return;
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = _dummyNode;
while(index--) cur = cur->next;
newNode->next = cur->next;
cur->next = newNode;
_size++;
}
void deleteAtIndex(int index) {
if(index >= _size || index < 0)return;
LinkedNode* cur = _dummyNode;
while(index--) cur = cur->next;
LinkedNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
_size--;
}
private:
int _size;
LinkedNode* _dummyNode;
};
/**
* 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. Reverse Linked List**
<two pointer>
```cpp=
/**
* 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) {
ListNode* pre = NULL;
ListNode* cur = head;
ListNode* tmp;
while(cur){
tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
};
```
<遞歸解>
```cpp=
class Solution {
public:
ListNode* reverse(ListNode* pre, ListNode* cur){
if(!cur)return pre;
ListNode* tmp = cur->next;
cur->next = pre;
return reverse(cur, tmp);
}
ListNode* reverseList(ListNode* head) {
return reverse(NULL, head);
}
};
```
**142. Linked List Cycle II**
```cpp=
/**
* 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* fast = head;
ListNode* slow = head;
while(fast != NULL && fast->next != NULL){
fast = fast->next->next;
slow = slow->next;
if(fast == slow){
ListNode* index1 = fast;
ListNode* index2 = head;
while(index1 != index2){
index1 = index1->next;
index2 = index2->next;
}
return index2;
}
}
return NULL;
}
};
```
<h1>哈希表</h1>
**242. Valid Anagram**
```cpp=
class Solution {
public:
bool isAnagram(string s, string t) {
int record[26]={0};
for(int i = 0; i < s.size(); i++) record[s[i] - 'a']++;
for(int i = 0; i < t.size(); i++) record[t[i] - 'a']--;
for(int i = 0; i < 26; i++) if(record[i]) return false;
return true;
}
};
```
**349. Intersection of Two Arrays**
```cpp=
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set;
unordered_set<int> num_set(nums1.begin(),nums1.end());
for(int num : nums2){
if(num_set.find(num) != num_set.end()){
result_set.insert(num);
}
}
return vector<int>(result_set.begin(),result_set.end());
}
};
```
**202. Happy Number**
```cpp=
class Solution {
public:
int toSum(int n){
int sum = 0;
while(n){
sum += (n % 10) * (n % 10);
n /= 10;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int> set;
while(1){
int num = toSum(n);
if(num == 1) return true;
if(set.find(num) != set.end()) return false;
else set.insert(num);
n = num;
}
}
};
```
**1. Two Sum**
```cpp=
// 使用 std::unordered_map
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
std::unordered_map <int,int> map;
for(int i = 0; i < nums.size(); i++) {
auto iter = map.find(target - nums[i]);
if(iter != map.end()) return {iter->second, i};
// map::insert({key, element})
map.insert({nums[i], i});
}
return {};
}
};
```
**383. Ransom Note**
```cpp=
//暴力解
//時間複雜度O(n^2)
//空間複雜度O(1)
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
for(int i = 0; i < magazine.length(); i++){
for(int j = 0; j < ransomNote.length(); j++){
if(magazine[i] == ransomNote[j]){
ransomNote.erase(ransomNote.begin() + j);
break;
}
}
}
if(!ransomNote.length()) return true;
return false;
}
};
```
```cpp=
//哈希解法 - 數組在哈希法中的應用
//時間複雜度O(n)
//空間複雜度O(1)
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int record[26] = {0};
for(char a : magazine) record[a - 'a']++;
for(char a : ransomNote){
record[a - 'a']--;
if(record[a - 'a'] < 0) return false;
}
return true;
}
};
```
**15. 3Sum**
```cpp=
//哈希法
//時間複雜度O(n^2)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
// 宣告二維vector
sort(nums.begin(),nums.end());
for(int i = 0; i < nums.size(); i++){
if(nums[i] > 0)
continue;
if(i > 0 && nums[i] == nums[i-1])
continue;
unordered_set<int> set;
for(int j = i+1; j < nums.size(); j++){
if(j > i+2 && nums[j] == nums[j-1] && nums[j-1] == nums[j-2])
continue;
int c = 0 - (nums[i] + nums[j]);
if(set.find(c) != set.end()){
result.push_back({nums[i], nums[j], c});
//push_back 插到最後面
set.erase(c);
//Q : unordered_set.erase(a) 是把所有a都清除嗎(假設容器裡面至少有2個a) 還是只刪一個?
//A : unordered_set中不存在重複的值
}
else set.insert(nums[j]);
}
}
return result;
}
};
```
```cpp=
//雙指針法
//時間複雜度O(n^2)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(),nums.end());
for(int i = 0; i < nums.size(); i++){
if(nums[i] > 0) return result;
if(i > 0 && nums[i] == nums[i-1]) continue;
int left = i + 1;
int right = nums.size() - 1;
while(right > left){
if(nums[i] + nums[left] + nums[right] > 0) right--;
else if (nums[i] + nums[left] + nums[right] < 0) left++;
else {
result.push_back({nums[i], nums[left], nums[right]});
// right > left && 易忘
while(right > left && nums[left] == nums[left + 1]) left++;
while(right > left && nums[right] == nums[right - 1]) right--;
right--;
left++;
}
}
}
return result;
}
};
```
**18. 4Sum**
```cpp=
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size(); i++){
if(i > 0 && nums[i]==nums[i-1])continue;
int64_t t1 = target-nums[i]; // int64_t
for(int j = i + 1; j < nums.size(); j++){
if(j > i + 1 && nums[j]==nums[j-1])continue;
int64_t t2 = t1-nums[j]; // int64_t
int left = j + 1;
int right = nums.size()-1;
while(right > left){
// prevent int overflow
if(nums[left]+nums[right] > t2) right--;
else if(nums[left]+nums[right] < t2) left++;
else{
result.push_back({nums[i], nums[j], nums[left], nums[right]});
while(right > left && nums[left] == nums[left + 1]) left++;
while(right > left && nums[right] == nums[right - 1]) right--;
right--;
left++;
}
}
}
}
return result;
}
};
```
<h1>字符串</h1>
**344. Reverse String**
```cpp=
class Solution {
public:
void reverseString(vector<char>& s) {
for(int i = 0, j = s.size()-1; i < s.size()/2; i++,j--){
swap(s[i],s[j]);
}
}
};
```
**541. Reverse String II**
```cpp=
class Solution {
public:
string reverseStr(string s, int k) {
for(int i = 0; i < s.size(); i += 2*k){
if(i + k <= s.size()){
reverse(s.begin() + i, s.begin() + i + k);
continue;
}
reverse(s.begin() + i, s.end());
}
return s;
}
};
```
**151. Reverse Words in a String**
```cpp=
class Solution {
public:
//單字翻轉
void reverse(string& s, int start, int end) {
while(start < end){
swap(s[start], s[end]);
start++;
end--;
}
}
//去除多餘空白
void removeExtraSpaces(string& s) {
int slowIndex = 0, fastIndex = 0;
// 去除字串前面的空格
while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ')
fastIndex++;
for (; fastIndex < s.size(); fastIndex++) {
// 去除字串中間部分的冗餘空格
if (fastIndex - 1 > 0 &&
s[fastIndex - 1] == s[fastIndex] && s[fastIndex] == ' ')
continue;
else
s[slowIndex++] = s[fastIndex];
}
if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') // 去除字串末的空格
s.resize(slowIndex - 1);
else
s.resize(slowIndex); // 重新設定字串大小
}
string reverseWords(string s) {
removeExtraSpaces(s);
reverse(s, 0, s.size() - 1);
int start, end = 0;
bool entry = false;
for (int i = 0; i < s.size(); i++) {
if ((!entry) || (s[i] != ' ' && s[i - 1] == ' ')) {
start = i;
entry = true;
}
if (entry && s[i] == ' ' && s[i - 1] != ' ') {
end = i - 1;
entry = false;
reverse(s, start, end);
}
if (entry && (i == (s.size() - 1)) && s[i] != ' ' ) {
end = i;
entry = false;
reverse(s, start, end);
}
}
return s;
}
};
```
**28. Implement strStr()**
```cpp=
//KMP
//原始版前綴表 (沒有將整個表右移 或 -1)
class Solution {
public:
void getNext(int* next, const string& s){
int j = 0;
next[0] = j;
for(int i = 1; i < s.size(); i++){
while(j > 0 && s[i] != s[j]) j = next[j-1];
if (s[i] == s[j]) j++;
next[i] = j;
}
}
// 匹配字串 模式串
int strStr(string haystack, string needle) {
if(needle.size() == 0) return 0;
int j = 0;
int next[needle.size()];
getNext(next, needle);
for(int i = 0; i < haystack.size(); i++){
while(j > 0 && haystack[i] != needle[j]) j = next[j-1];
if(haystack[i] == needle[j]) j++;
if(j == needle.size()) return i - needle.size() + 1;
}
return -1;
}
};
```
**459. Repeated Substring Pattern**
```cpp=
//前綴表
class Solution {
public:
void getNext(int* next, const string& s){
int j = 0;
next[0] = j;
for(int i = 1; i < s.size(); i++){
while(j > 0 && s[i] != s[j]) j = next[j-1];
if (s[i] == s[j]) j++;
next[i] = j;
}
}
bool repeatedSubstringPattern(string s) {
int len = s.size();
int next[len];
getNext(next, s);
/* 若 len % (len - next[len-1]) == 0 則 return True
len可被len-s的長相等前後綴長度 整除
len-s的長相等前後綴長度 為 最小重覆子字串長度
12 % (12-9)
s = "abcabcabcabc"
next[]= 000123456789
s = "abab"
next[]= 0012
s = "abac"
next[]= 0010
最後一位不可為0
*/
if (len % (len - next[len-1]) == 0 && next[len - 1] != 0) return true;
return false;
}
};
```
<h1>Stack & Queue</h1>
**232. Implement Queue using Stacks**
```cpp=
class MyQueue {
public:
stack<int> stIn;
stack<int> stOut;
MyQueue() {
}
void push(int x) {
stIn.push(x);
}
int pop() {
if(stOut.empty()){
while(!stIn.empty()){
stOut.push(stIn.top());
stIn.pop();
}
}
int temp = stOut.top();
stOut.pop();
return temp;
}
int peek() {
int res = this->pop();
stOut.push(res);
return res;
}
bool empty() {
return stIn.empty() && stOut.empty();
}
};
/**
* 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. Implement Stack using Queues**
```cpp=
//用兩個stack實現 (一個用來備份
class MyStack {
public:
queue<int> que1;
queue<int> que2;
MyStack() {
}
void push(int x) {
que1.push(x);
}
int pop() {
int size = que1.size();
while(size != 1){
que2.push(que1.front());
que1.pop();
size--;
}
int res = que1.front();
que1 = que2;
while(!que2.empty()) //clear que2
que2.pop();
return res;
}
int top() {
return que1.back(); //last X:front()
}
bool empty() {
return que1.empty();
}
};
/**
* 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();
*/
```
```cpp=
//用一個stack實現
class MyStack {
public:
queue<int> que1;
MyStack() {
}
void push(int x) {
que1.push(x);
}
int pop() {
int size = que1.size();
while(size != 1){
que1.push(que1.front());//把最後一個前面的push到它後面
que1.pop();
size--;
}
int res = que1.front();
que1.pop();
return res;
}
int top() {
return que1.back();
}
bool empty() {
return que1.empty();
}
};
```
**20. Valid Parentheses**
```cpp=
class Solution {
public:
bool isValid(string s) {
stack<char> st;
for(int i = 0; i < s.size(); i++){
if(s[i] == '(') st.push(')');
else if (s[i] == '[') st.push(']');
else if (s[i] == '{') st.push('}');
else if (st.empty() || s[i] != st.top()) return false;
else st.pop();
}
return st.empty();
}
};
```
**1047. Remove All Adjacent Duplicates In String**
```cpp=
class Solution {
public:
string removeDuplicates(string S) {
stack<char> st;
for(char s:S){
if(st.empty() || s != st.top()) st.push(s);
else st.pop();
}
string res = "";
while(!st.empty()){
res += st.top();
st.pop();
}
reverse(res.begin(), res.end());
return res;
}
};
```
**150. Evaluate Reverse Polish Notation**
```cpp=
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
for(int i = 0; i < tokens.size(); i++){
// v 不可用'
if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"){
int num2 = st.top();
st.pop();
int num1 = st.top();
st.pop();
if(tokens[i] == "+") st.push(num1 + num2);
if(tokens[i] == "-") st.push(num1 - num2);
if(tokens[i] == "*") st.push(num1 * num2);
if(tokens[i] == "/") st.push(num1 / num2);
}else{
st.push(stoi(tokens[i]));
}
}
return st.top();
}
};
/*
單調隊列，即單調遞減或單調遞增的隊列
*/
```
**239. Sliding Window Maximum**
```cpp=
class Solution {
private:
// 單調隊列，即單調遞減或單調遞增的隊列 (這邊使用單調遞增)
class Mydeque{
public:
deque<int> que;
void pop(int value){
if(!que.empty() && value == que.front())
que.pop_front();
}
void push(int value){
while(!que.empty() && value > que.back())
que.pop_back();
que.push_back(value);
}
int front(){
return que.front();
}
};
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
Mydeque que;
for(int i = 0; i < k;i++)
que.push(nums[i]);
for(int i = k; i < nums.size(); i++){
result.push_back(que.front());
que.pop(nums[i-k]);
que.push(nums[i]);
}
result.push_back(que.front());
return result;
}
};
```
**347. Top K Frequent Elements**
```cpp=
class Solution {
public:
class cmp{
public:
bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs){
return lhs.second > rhs.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> map;
for(int i = 0; i < nums.size(); i++) // map<nums[i],出現次數>
map[nums[i]]++;
// priority_queue<T, vector<T>, cmp> pq; 自行定義 cmp 排序
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
for(unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++){
pq.push(*it);
if(pq.size() > k)
pq.pop();
}
// v 設定容器大小為k
vector<int> result(k);
for(int i = k -1; i >= 0 ;i--){
// v 用.first 因為 儲存的元素是pair
result[i] = pq.top().first;
pq.pop();
}
return result;
}
};
/*
什麼是優先級隊列(priority_queue)呢？
其實就是一個披著隊列外衣的堆，因為優先級隊列對外接口只是從隊頭取元素，
從隊尾添加元素，再無其他取元素的方式，看起來就是一個隊列。
而且優先級隊列內部元素是自動依照元素的權值排列。
如需改變priority_queue的優先權定義：
priority_queue<T> pq; 預設由大排到小
priority_queue<T, vector<T>, greater<T> > pq; 改成由小排到大
priority_queue<T, vector<T>, cmp> pq; 自行定義 cmp 排序
*/
```
<h1>Binary Tree</h1>
**144. Binary Tree Preorder Traversal**
```cpp=
/*
* 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 traversal(TreeNode* cur, vector<int>& vec){
if (cur == NULL)return;
vec.push_back(cur->val);
traversal(cur->left, vec);
traversal(cur->right, vec);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};
/*
C++中map、set、multimap，multiset的底層實現都是平衡二叉搜索樹，所以map、set的增刪操作時間時間複雜度是logn，
unordered_map、unordered_map底層實現是哈希表。
二叉樹的定義
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
*/
//--------------------------------------------------------------------------
// nonrecursive
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> st;
if(!root) return result;
st.push(root);
while(!st.empty()){
TreeNode* node = st.top();
st.pop();
result.push_back(node->val);
if (node->right) st.push(node->right);
if (node->left ) st.push(node->left);
}
return result;
}
};
//--------------------------------------------------------------------------
// 迭代法
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
if(root) st.push(root);
while(!st.empty()){
TreeNode* node = st.top();
if(node){
st.pop();
if(node->right) st.push(node->right);
if(node->left) st.push(node->left);
st.push(node);
st.push(NULL);
}else{
st.pop();
node = st.top();
st.pop();
result.push_back(node->val);
}
}
return result;
}
};
```
**145. Binary Tree Postorder Traversal**
```cpp=
/**
* 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 traversal(TreeNode* cur, vector<int>& vec){
if(cur == NULL)return;
traversal(cur->left, vec);
traversal(cur->right, vec);
vec.push_back(cur->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};
//--------------------------------------------------------------------------
// nonrecursive
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
if(!root) return result;
st.push(root);
while(!st.empty()){
TreeNode* node = st.top();
result.push_back(node->val);
st.pop();
if(node->left ) st.push(node->left);
if(node->right) st.push(node->right);
}
reverse(result.begin(), result.end());
return result;
}
};
//--------------------------------------------------------------------------
// 迭代法
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
if(root) st.push(root);
while(!st.empty()){
TreeNode* node = st.top();
if(node){
st.pop();
st.push(node);
st.push(NULL);
if(node->right) st.push(node->right);
if(node->left) st.push(node->left);
}else{
st.pop();
node = st.top();
st.pop();
result.push_back(node->val);
}
}
return result;
}
};
```
**94. Binary Tree Inorder Traversal**
```cpp=
/**
* 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 traversal(TreeNode* cur, vector<int>& vec){
if(cur == NULL)return;
traversal(cur->left, vec);
vec.push_back(cur->val);
traversal(cur->right, vec);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};
//--------------------------------------------------------------------------
// nonrecursive
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
TreeNode* cur = root;
while(cur || !st.empty()){
if(cur){
st.push(cur);
cur = cur->left;
}else{
cur = st.top();
result.push_back(cur->val);
st.pop();
cur = cur->right;
}
}
return result;
}
};
//--------------------------------------------------------------------------
// 迭代法
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> result;
if(root) st.push(root);
while(!st.empty()){
TreeNode* node = st.top();
if(node){
st.pop();
if(node->right) st.push(node->right);
st.push(node);
st.push(NULL);
if(node->left) st.push(node->left);
}else{
st.pop();
node = st.top();
st.pop();
result.push_back(node->val);
}
}
return result;
}
};
```
**102. Binary Tree Level Order Traversal**
```cpp=
/**
* 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) {
queue<TreeNode*> que;
vector<vector<int>> result;
if(root) que.push(root);
while(!que.empty()){
int size = que.size();
vector<int> vec;
for(int i = 0; i < size; i++){
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
}
result.push_back(vec);
}
return result;
}
};
//--------------------------------------------------------------------------
//Recursion
class Solution {
public:
void order(TreeNode* cur, vector<vector<int>>& result, int depth){
if(cur == nullptr)return;
if(result.size() == depth) result.push_back(vector<int>());
result[depth].push_back(cur->val);
order(cur->left, result, depth+1);
order(cur->right, result, depth+1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
int depth = 0;
order(root, result, depth);
return result;
}
};
// 相關題(9)
// 107.二叉樹的層次遍歷II
class Solution {
public:
void order(TreeNode* cur, vector<vector<int>>& result, int depth){
if(cur == nullptr)return;
if(result.size() == depth) result.push_back(vector<int>());
result[depth].push_back(cur->val);
order(cur->left, result, depth+1);
order(cur->right, result, depth+1);
}
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> result;
int depth = 0;
order(root, result, depth);
reverse(result.begin(), result.end());
return result;
}
};
// 199.二叉樹的右視圖
/**
* 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) {
queue<TreeNode*> que;
vector<int> result;
if(root) que.push(root);
while(!que.empty()){
int size = que.size();
vector<int> vec;
for(int i = 0; i < size; i++){
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
}
result.push_back(vec[vec.size()-1]);
}
return result;
}
};
// 637.二叉樹的層平均值
/**
* 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) {
queue<TreeNode*> que;
vector<double> result;
if(root) que.push(root);
while(!que.empty()){
int size = que.size();
vector<int> vec;
for(int i = 0; i < size; i++){
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
}
result.push_back(1.0 * accumulate(vec.begin(), vec.end(), 0) / vec.size());
}
return result;
}
};
// 429.N叉樹的層序遍歷
/*
// 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>> result;
if(!root)return result;
queue<Node*> que;
que.push(root);
while(!que.empty()){
vector<int> temp;
int size = que.size();
for(int i = 0; i < size; i++){
Node* node = que.front();
que.pop();
temp.push_back(node->val);
if (node->children.size() > 0)
for(auto child : node->children)
que.push(child);
}
result.push_back(temp);
}
return result;
}
};
// 515.在每個樹行中找最大值
/**
* 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> result;
queue<TreeNode*> q;
if(root) q.push(root);
while(!q.empty()){
int size = q.size();
vector<int> temp;
for(int i = 0; i < size; i++){
TreeNode* cur = q.front();
q.pop();
temp.push_back(cur->val);
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
}
result.push_back(*max_element(temp.begin(), temp.end()));
}
return result;
}
};
// 116.填充每個節點的下一個右側節點指針
/*
// 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 and root->left){
root->left->next = root->right;
if(root->next) root->right->next = root->next->left;
connect(root->left);
connect(root->right);
}
return root;
}
};
// 117.填充每個節點的下一個右側節點指針II
/*
// 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 NULL;
queue<Node*> q;
q.push(root);
while(!q.empty()){
int n = q.size();
for(int i = 0; i < n; i++){
Node* temp = q.front();
q.pop();
if(i == n-1) temp->next = NULL;
else temp->next = q.front();
if(temp->left) q.push(temp->left);
if(temp->right)q.push(temp->right);
}
}
return root;
}
};
// 104.二叉樹的最大深度
class Solution {
public:
int maxDepth(TreeNode* root) {
if(!root) return 0;
int left = maxDepth(root->left);
int right = maxDepth(root->right);
return max(left, right) + 1;
}
};
//類似104 559. Maximum Depth of N-ary Tree
/*
// 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 depth = 0;
queue<Node*> q;
if(!root) return 0;
q.push(root);
while(!q.empty()){
int n = q.size();
depth++;
for(int i = 0; i < n; i++){
Node* node = q.front(); q.pop();
if(node->children.size())
for(auto child : node->children)
q.push(child);
}
}
return depth;
}
};
//559 2
class Solution {
public:
int maxDepth(Node* root) {
int depth = 0;
if(!root) return 0;
if(root->children.size()){
for(auto child : root->children)
depth = max(depth, maxDepth(child));
}
return depth+1;
}
};
// 111.二叉樹的最小深度
class Solution {
public:
int minDepth(TreeNode* root) {
if(!root) return 0;
int left = minDepth(root->left);
int right = minDepth(root->right);
if(!min(left, right)) return max(left, right) + 1;
return min(left, right) + 1;
}
};
```
**226. Invert Binary Tree**
```cpp=
/**
* 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) return root;
swap(root->right, root->left);
invertTree(root->left);
invertTree(root->right);
return root;
}
};
//stack (in-order X)
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(!root) return root;
stack<TreeNode*> st;
st.push(root);
while(!st.empty()){
TreeNode* node = st.top();
st.pop();
swap(node->right, node->left);
if(node->right)st.push(node->right);
if(node->left)st.push(node->left);
}
return root;
}
};
// stack (通用)
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(!root) return root;
stack<TreeNode*> st;
st.push(root);
while(!st.empty()){
TreeNode* node = st.top();
if(node){
st.pop();
if(node->right)st.push(node->right);
if(node->left)st.push(node->left);
st.push(node);
st.push(NULL);
}else{
st.pop();
node = st.top();
st.pop();
swap(node->right, node->left);
}
}
return root;
}
};
```
**101. Symmetric Tree**
```cpp=
/**
* 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 cmp(TreeNode* left, TreeNode* right){
if(!left && right) return false;
else if(left && !right) return false;
else if(left == right && !left) return true;
else if(left->val != right->val) return false;
bool in = cmp(left->right, right->left);
bool out = cmp(left->left, right->right);
return in && out;
}
bool isSymmetric(TreeNode* root) {
if(!root) return true;
return cmp(root->left, root->right);
}
};
// 改
class Solution {
public:
bool cmp(TreeNode* left, TreeNode* right){
if(!left && !right) return true;
else if(!right || !left || left->val != right->val) return false;
return cmp(left->right, right->left) && cmp(left->left, right->right);
}
bool isSymmetric(TreeNode* root) {
if(!root) return true;
return cmp(root->left, root->right);
}
};
// queue
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(!root) return true;
queue<TreeNode*> q;
q.push(root->left);
q.push(root->right);
while(!q.empty()){
TreeNode* left = q.front(); q.pop();
TreeNode* right = q.front(); q.pop();
if(!left && !right) continue;
if(!left || !right || left->val != right->val) return false;
q.push(left->left);
q.push(right->right);
q.push(left->right);
q.push(right->left);
}
return true;
}
};
// stack
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(!root) return true;
stack<TreeNode*> st;
st.push(root->right);
st.push(root->left);
while(!st.empty()){
TreeNode* left = st.top(); st.pop();
TreeNode* right = st.top(); st.pop();
if(!left && !right) continue;
if(!left || !right || left->val != right->val) return false;
st.push(left->left);
st.push(right->right);
st.push(left->right);
st.push(right->left);
}
return true;
}
};
//100. Same Tree
/**
* 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 cmp(TreeNode* p, TreeNode* q){
if(!p && !q)return true;
else if(!p || !q || p->val != q->val) return false;
return cmp(p->right, q->right) && cmp(p->left, q->left);
}
bool isSameTree(TreeNode* p, TreeNode* q) {
if(!p && !q) return true;
return cmp(p, q);
}
};
//572. Subtree of Another Tree
/**
* 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 cmp(TreeNode* p, TreeNode* q){
if(!p && !q)return true;
else if(!p || !q || p->val != q->val) return false;
return cmp(p->right, q->right) && cmp(p->left, q->left);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if(!root) return false;
return cmp(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
};
```
Google Drive
Gist
Clipboard
Sign in with Wallet
