# LeetCode | Data Structure I | 14 Days Challenge | Day 9-10
###### tags: `LeetCode` `Data Structure I` `14 Days Challenge`
## Day 9
### [20. Valid Parentheses](https://leetcode.com/problems/valid-parentheses/?envType=study-plan&id=data-structure-i)
### 題目敘述
>*Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.*
>*An input string is valid if:*
>*Open brackets must be closed by the same type of brackets.*
>*Open brackets must be closed in the correct order.*
>*Every close bracket has a corresponding open bracket of the same type.*
### 測資
Example 1:
:::info
Input: s = "()"
Output: true
:::
Example 2:
:::info
Input: s = "()[]{}"
Output: true
:::
Example 3:
:::info
Input: s = "(]"
Output: false
:::
### 數值範圍
1 <= s.length <= 10^4^
s consists of parentheses only '()[]{}'.
### 核心概念
==stack==
### 想法
今天是第九天！Stack & Queue Day！
這兩個資料結構算是新手入門的好切入點！非常好玩
這兩種資料結構很相似，但卻截然不同！
* Stack
擁有FILO(First-In-Last-Out)先入後出特性，常用演算法為DFS。
* Queue
擁有FIFO(First-In-First-Out)先入後出特性，常用演算法為BFS。
不知道DFS、BFS是甚麼？明後天就會知道了~
本題利用stack特性，當遇到左括號便push進stack中，遇到右括號則進行判斷，若相符合則將top的括號pop出來~同時要注意stack是否為空，若遇到右括號，而且stack為空，也視為不合法，則return false，**做題目都要要注意題目的界限**
***time : 10-15 mins
time complexity : $O(n)$
space complexity : $O(n)$***
### 程式碼
```c++=1
class Solution {
public:
bool isValid(string s) {
int len = s.size();
stack<char> sk;
if (len == 1) return false;
for (auto chr : s) {
if (chr == '(' || chr == '{' || chr == '[') sk.push(chr);
else if(!sk.empty()){
if (sk.top() == '(' && chr == ')') sk.pop();
else if (sk.top() == '[' && chr == ']') sk.pop();
else if (sk.top() == '{' && chr == '}') sk.pop();
else return false;
}
else return false;
}
if (!sk.empty()) return false;
else return true;
}
};
```
### [232. Implement Queue using Stacks](https://leetcode.com/problems/merge-two-sorted-lists/?envType=study-plan&id=data-structure-i)
### 題目敘述
>*Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).*
>*Implement the MyQueue class:*
>*void push(int x) Pushes element x to the back of the queue.*
>
>* int pop() Removes the element from the front of the queue and returns it.
>* int peek() Returns the element at the front of the queue.
>* boolean empty() Returns true if the queue is empty, false otherwise.
>Notes:
>* You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
>* Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.
### 測資
Example 1:
:::info
Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]
Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
:::
### 數值範圍
1 <= x <= 9
At most 100 calls will be made to push, pop, peek, and empty.
All the calls to pop and peek are valid.
### 核心概念
==stack、queue==
### 想法
非常特別的題目，利用兩個stack來實現queue特性，官方解答的圖清楚的解釋了實現過程。
當有value push進stack s1，先將原本s1的alue丟到stack s2，value順序便會顛倒，最後再將s2的value盡數丟回s1，即完成數字的顛倒，需要pop則直接取用上方的值即可。
***time : 10~15 mins
time complexity : $O(n)$
space complexity : $O(1)$***
### 程式碼
```c++=1
class MyQueue {
public:
stack<int> sk1,sk2;
MyQueue() {
}
void push(int x) {
while(!sk1.empty()) {
sk2.push(sk1.top());
sk1.pop();
}
sk2.push(x);
while(!sk2.empty()) {
sk1.push(sk2.top());
sk2.pop();
}
}
int pop() {
int p = sk1.top();
sk1.pop();
return p;
}
int peek() {
return sk1.top();
}
bool empty() {
return sk1.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();
*/
```
## Day 10
### [144. Binary Tree Preorder Traversal](https://leetcode.com/problems/remove-linked-list-elements/?envType=study-plan&id=data-structure-i)
### 題目敘述
>*Given the root of a binary tree, return the preorder traversal of its nodes' values.*
### 測資
Example 1:
:::info
Input: root = [1,null,2,3]
Output: [1,2,3]
:::
Example 2:
:::info
Input: root = []
Output: []
:::
Example 3:
:::info
Input: root = [1]
Output: [1]
:::
### 核心概念
==tree、Preorder Traversal、DFS==
### 數值範圍
The number of nodes in the list is in the range [0, 10^4^].
1 <= Node.val <= 50
0 <= val <= 50
### 想法
Traversal有四種。先介紹前三種。
* Preorder : 前序搜尋
輸出值順序 : **root** -> left -> right
* Inorder : 中序搜尋
輸出值順序 : left -> **root** -> right
* Postorder : 後序搜尋
輸出值順序 : left -> right -> **root**
你會發現分辨搜尋的方法便是依root的輸出順序而定。
本題為Preorder，利用DFS(Depth-First Search(深度優先搜尋)演算法，搭配遞迴實現~算是基礎的演算法題。
***time : 3 mins
time complexity : $O(n)$
space complexity : $O(n)$***
### 程式碼
```c++=1
/**
* 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> ans;
void dfs(TreeNode* node){
if(node == nullptr) return;
ans.push_back(node->val);
dfs(node->left);
dfs(node->right);
}
vector<int> preorderTraversal(TreeNode* root) {
dfs(root);
return ans;
}
};
```
### [94. Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/description/?envType=study-plan&id=data-structure-i)
### 題目敘述
>*Given the root of a binary tree, return the inorder traversal of its nodes' values.*
### 測資
Example 1:
:::info
Input: root = [1,null,2,3]
Output: [1,3,2]
:::
Example 2:
:::info
Input: root = []
Output: []
:::
Example 3:
:::info
Input: root = [1]
Output: [1]
:::
### 核心概念
==tree、Inorder Traversal、DFS==
### 數值範圍
The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100
### 想法
如上題所述，將遞迴程式碼兩行調換，即達成Inorder Traversal。
***time : 3 mins
time complexity : $O(n)$
space complexity : $O(n)$***
### 程式碼
```c++=1
/**
* 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> ans;
void dfs(TreeNode* node){
if(node == nullptr) return;
dfs(node->left);
ans.push_back(node->val);
dfs(node->right);
}
vector<int> inorderTraversal(TreeNode* root) {
dfs(root);
return ans;
}
};
```
### [145. Binary Tree Postorder Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/description/?envType=study-plan&id=data-structure-i)
### 題目敘述
>*Given the root of a binary tree, return the postorder traversal of its nodes' values.*
### 測資
Example 1:
:::info
Input: root = [1,null,2,3]
Output: [3,2,1]
:::
Example 2:
:::info
Input: root = []
Output: []
:::
Example 3:
:::info
Input: root = [1]
Output: [1]
:::
### 核心概念
==tree、Postorder Traversal、DFS==
### 數值範圍
The number of the nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100
### 想法
如上題所述，將遞迴程式碼兩行調換，即達成Postorder Traversal。
***time : 3~5 mins
time complexity : $O(n)$
space complexity : $O(n)$***
### 程式碼
```c++=1
/**
* 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> ans;
void dfs(TreeNode* node){
if(node == nullptr) return;
dfs(node->left);
dfs(node->right);
ans.push_back(node->val);
}
vector<int> postorderTraversal(TreeNode* root) {
dfs(root);
return ans;
}
};
```
Sign in with Wallet
Connect another wallet