# 演算法作業八

## 觀念題
### 第1題: Voronoi Diagram
- 請畫出下圖兩個VD合併結果，畫出新建立的線段(註明為哪兩點的中垂線)，並說明簡述流程
- 流程
1. 尋找$S_L$與$S_R$的凸包
2. 找到$hull(S_L)$與$hull(S_R)$的公切線$P_1,P_2$($P_1$在上面)
- $SG = P_1$
- $HP = \emptyset$
3. 找到SG的中垂線BS
- $HP = HP U BS$
- 如果$SG = P_2$，goto step5
4. 找到下一邊，並更新$SG$
5. 將延伸的線discard，並執行合併
- 過程
### 第2題: Voronoi Diagram的應用
- 請說明The Euclidean all nearest neighbor problem為何，以及如何應用VD來解此問題？
- Input: 一個點A
- Ooutput: 找到離點A最近的點P
- 方法
- 用VD 演算法產生圖
- 將VD劃分的區域產生的每一個點畫出水平線 => 產生多個region
- 先將客人位置找出在哪一條平線
- 再將客人位置找出在哪一條平線的region
### 第3題: FFT
- 當輸入為：{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}，請說明如何應用FFT得到結果(只須說明計算過程，不用算出結果)？
1. 如果 size == 2
- $b_0 = a_0+a_1$
- $b_1 = a_0-a_1$
- Divide
2. 將array分成兩個
- $\{a_0,a_2\dots\}$
- $\{a_1,a_3\dots\}$
- Merge
3. 合併兩array
- $b_j = c_j + w^{-j}d_j$
- $b_j+n/2 = c_j - w^{-j}d_j$
- 計算過程
## 程式題

### 第4題: 由Preorder與Inorder建構二元樹
[leetcode 105](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/)
- 程式碼
:::spoiler C++

    class Solution {
    public:
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            int root = 0;
            return build(preorder,inorder,root,0,inorder.size()-1);
        }
    private:
        TreeNode* build(vector<int>& preorder, vector<int>& inorder,int& root,int left,int right){
            typedef TreeNode* nodePtr;
            if (left > right) return NULL;
            int mid = left;
            while (inorder[mid] != preorder[root]) mid++;

            root++;
            nodePtr newNode = new TreeNode(inorder[mid]);
            newNode->left  = build(preorder,inorder,root,left,mid-1);
            newNode->right = build(preorder,inorder,root,mid+1,right);

            return newNode;
        }
    };

:::
- 執行結果
- 花費時間: 10分鐘
- 完成程度: 靠自己
- 思路
- ~~資料結構作業有ㄟ酷酷酷~~
- 切入點: preorder中，第一個就是中間
- 找到中間的節點 => 製作出一個左右為null之節點
- Divide
- 將inorder切成兩個子樹，並繼續遞迴的生成
- Merge
- 將左子樹與右子樹接上中間節點就好了
### 第5題: 由Postorder與Inorder建構二元樹
[leetcode 106](https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/)
- 程式碼
:::spoiler C++

    class Solution {
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            int root = postorder.size() - 1;
            return build(postorder,inorder,root,0,inorder.size()-1);
        }
    private:
        TreeNode* build(vector<int>& postorder, vector<int>& inorder,int& root,int left,int right){
            typedef TreeNode* nodePtr;
            if (left > right) return NULL;
            int mid = left;
            while (inorder[mid] != postorder[root]) mid++;

            root--;
            nodePtr newNode = new TreeNode(inorder[mid]);
            newNode->right = build(postorder,inorder,root,mid+1,right);
            newNode->left  = build(postorder,inorder,root,left,mid-1);


            return newNode;
        }
    };

:::
- 執行結果
- 花費時間: 10分鐘
- 完成程度: 靠自己
- 思路
- 切入點: postorder的中間節點是從後面開始的
- 找到中間的節點 => 製作出一個左右為null之節點
- Divide
- 將inorder切成兩個子樹，並繼續遞迴的生成
- Merge
- 將左子樹與右子樹接上中間節點就好了
### 第6題：由Pretorder與Postorder建構二元樹
[leetcode 889](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/)
- 程式碼
:::spoiler C++

    class Solution {
    typedef TreeNode* nodePtr; 
    private:
        unordered_map<int,int> hashTable;
        int root = 0;
    public:
        nodePtr constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
            for (int i=0;i<postorder.size();i++) hashTable[postorder[i]] = i;

            return  bulid(preorder,postorder,0, postorder.size()-1);
        }
        nodePtr bulid(vector<int>& preorder, vector<int>& postorder, int left,int right){
            if (left>right || root>=preorder.size()) return NULL;

            int val = preorder[root++];

            nodePtr node = new TreeNode(val);
            if (root >= preorder.size() || left==right) return node;

            int post = hashTable[preorder[root]];
            node -> left  = bulid(preorder,postorder,left,post);
            node -> right = bulid(preorder,postorder,post+1,right-1);

            return node; 
        }
    };

:::
- 執行結果
- 花費時間: 1小時
- 完成程度: 有參考他人
- [ref](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/solutions/3617169/easy-to-understand-97-beats-c/)
- 思路
- 卡點: 我一直想說怎麼可能有唯一解 :(
- 其實概念跟上面差不多
- 找到中間的節點(這邊以preorder找) => 製作出一個左右為null之節點
- Divide
- 將postorder切成兩個子樹，並繼續遞迴的生成
- 需要注意的是，因為中間節點在右邊所以記得要剔除掉範圍內
- Merge
- 將左子樹與右子樹接上中間節點就好了
## 心得
這周繼續上周的進度D&C，學了VD與FFT，一開始以為FFT最難，結果後來發現VD才是大魔王，後來實際操作看看才比較熟悉一點點，感覺困難度超高0.0。

FFT之前在影像處理聽過，我看到數學式還覺得這個東西看起來好難，結果沒想到他居然是用分治法，真佩服想出這些演算法的人。

作業的部分，資料結構就被強迫寫了，所以體感上覺得很輕鬆，真棒。