---
# System prepended metadata

title: LeetCode | Data Structure I | 14 Days Challenge | Day 9-10
tags: [Data Structure I, LeetCode, 14 Days Challenge]

---

# 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則直接取用上方的值即可。

![](https://i.imgur.com/i9LF0ei.png)


***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:

![](https://i.imgur.com/yhTczWH.png)


:::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:

![](https://i.imgur.com/HgU8fU4.png)


:::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:

![](https://i.imgur.com/p5stKg6.png)



:::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;
    }
};
```
