# **演算法作業 HW8**
<font size=5>**1. Voronoi Diagram**</font>
---
* 請畫出下圖兩個VD合併結果，畫出新建立的線段(註明為哪兩點的中垂線)，並說明簡述流程。
ans：新建立線段(綠色)、輔助線(藍色、紅色)
首先將兩個VD的凸包合併，得到新的凸包。
接著從新得到的連線(b15 or b26)開始畫中垂線。
若線段跟其他中垂線交錯則轉折，置換成其他點的中垂線。
(基本上就是置換成兩條交錯中垂線中三個點的第三條中垂線)
畫完最後兩點，將超出的部分去除就完成了。
<font size=5>**2. Voronoi Diagram的應用**</font>
---
* 請說明The Euclidean all nearest neighbor problem為何，以及如何應用VD來解此問題？
ans：
找出距離給定點最近的點，利用VD圖劃分出的區域可以很輕鬆得到答案。
先將VD圖的每一點畫出互相平行的切線，得到許多平條區。
而每個平條區又被劃分成許多區域。
先找出點屬於哪一個平條，再找出屬於平條內哪個區域就解決了。
<font size=5>**3. FFT**</font>
---
* 當輸入為：{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}，請說明如何應用FFT得到結果(只須說明計算過程，不用算出結果)？
ans：
利用分治法的思維，每次分成奇數項跟偶數項(重複利用算過的結果來節省計算)。
不斷分割到最小問題後再往回算出更大的問題，直到計算出最後的結果。
<font size=6>**程式題:Divide and Conquer**</font>
---
<font size=5>**4. 由Preorder與Inorder建構二元樹**</font>
---
[Construct Binary Tree from Preorder and Inorder Traversal - LeetCode](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)
只要清楚前序跟中序的排列方式，就可以輕鬆的推導出答案了。
前序排列可以想成 **{ 父節點、{左子樹}、{右子樹} }**。
中序排列可以想成 **{ {左子樹}、父節點、{右子樹} }**。
構造時從前序中提出父節點，接著再呼叫左子樹右子樹的構造。
不斷重複上述步驟，直到構建完樹為止。
而子樹範圍可以從中序得出，藉此從前序中取出左子樹及右子樹呼叫。
完全靠自己，完成時間：十分鐘。
```c++
/**
* 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* buildTree(vector<int>& preorder, vector<int>& inorder) {
unordered_map<int,int> mp;
for(int i=0;i<inorder.size();++i)
mp[inorder[i]]=i;//用map紀錄元素在inorder內的索引
//用map去存的前提是元素不能重複
TreeNode* root = construct(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1,mp);
return root;
}
TreeNode* construct(vector<int>&preorder, int preStart, int preEnd, vector<int> &inorder,int inStart, int inEnd,unordered_map<int,int> &mp){
if(preStart>preEnd || inStart>inEnd) return NULL;
TreeNode* root = new TreeNode(preorder[preStart]);
int inRoot = mp[root->val];
int numsLeft = inRoot-inStart;//左子樹的點數量
root->left = construct(preorder,preStart+1,preStart+numsLeft,inorder,inStart,inRoot-1,mp);
root->right = construct(preorder,preStart+numsLeft+1,preEnd,inorder,inRoot+1,inEnd,mp);
return root;
}
};
```
<font size=5>**5. 由Postorder與Inorder建構二元樹**</font>
---
[Construct Binary Tree from Inorder and Postorder Traversal - LeetCode](https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/)
跟上一題同樣道理，只要搞清楚後序跟中序的排列就沒什麼難的。
後序排列可以想成 **{{左子樹}、{右子樹}，父節點 }**。
中序排列可以想成 **{ {左子樹}、父節點、{右子樹} }**。
構造時從後序中提出父節點，接著再呼叫左子樹右子樹的構造。
不斷重複上述步驟，直到構建完樹為止。
而子樹範圍可以從中序得出，藉此從後序中取出左子樹及右子樹呼叫。
完全靠自己，完成時間：五分鐘。
```c++
/**
* 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* buildTree(vector<int>& inorder, vector<int>& postorder) {
unordered_map<int,int> mp;
for(int i=0;i<inorder.size();++i)
mp[inorder[i]]=i;//用map紀錄元素在inorder內的索引
//用map去存的前提是元素不能重複
TreeNode* root = construct(postorder,0,postorder.size()-1,inorder,0,inorder.size()-1,mp);
return root;
}
TreeNode* construct(vector<int>&postorder, int postStart, int postEnd, vector<int> &inorder,int inStart, int inEnd,unordered_map<int,int> &mp){
if(postStart>postEnd || inStart>inEnd) return NULL;
TreeNode* root = new TreeNode(postorder[postEnd]);
int inRoot = mp[root->val];
int numsRight = inEnd-inRoot;//右子樹的點數量
root->left = construct(postorder,postStart,postEnd-numsRight-1,inorder,inStart,inRoot-1,mp);
root->right = construct(postorder,postEnd-numsRight,postEnd-1,inorder,inRoot+1,inEnd,mp);
return root;
}
};
```
<font size=5>**6. 由Pretorder與Postorder建構二元樹**</font>
---
[Construct Binary Tree from Preorder and Postorder Traversal - LeetCode](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/)
前序和後序並不能保證一個二元樹的構造，但是不影響構建出一個二元樹。
步驟跟前面相同，透過前序跟後序的特性取得左右子樹的根節點。
呼叫遞迴將二元樹構造出來就行了。
要注意的是，這三題的值都不會重複，所以才用map方便查找。
如果有重複的值就不能這樣做。
完全靠自己，完成時間：五分鐘。
```c++
/**
* 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* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
unordered_map<int,int> mp;
for(int i=0;i<postorder.size();++i)
mp[postorder[i]]=i;//用map紀錄元素在postorder內的索引
//用map去存的前提是元素不能重複
TreeNode* root = construct(preorder,0,preorder.size()-1,postorder,0,postorder.size()-1,mp);
return root;
}
TreeNode* construct(vector<int>&preorder, int preStart, int preEnd, vector<int>&postorder,int postStart, int postEnd,unordered_map<int,int> &mp){
if(preStart>preEnd || postStart>postEnd) return NULL;
TreeNode* root = new TreeNode(preorder[preStart]);
if(preStart == preEnd) return root;//剩一個節點時直接回傳，不然下面會出錯
int Lv = preorder[preStart+1];//左子樹根節點的值
int postLeftRoot = mp[Lv];//左子樹根節點在後序中索引
int numsLeft = postLeftRoot-postStart+1;//左子樹的點數量
root->left = construct(preorder,preStart+1,preStart+numsLeft,postorder,postStart,postLeftRoot,mp);
root->right = construct(preorder,preStart+numsLeft+1,preEnd,postorder,postLeftRoot+1,postEnd-1,mp);
return root;
}
};
```
<font size=5>**7. 本周心得**</font>
---
這周的題目之前做過了，只要搞懂特性就沒什麼困難的，很好理解。
---
若有錯誤歡迎指正
Sign in with Wallet
Connect another wallet