# 1103757 喬伊波伊 演算法作業8
## 第1題: Voronoi Diagram
* 請畫出下圖兩個VD合併結果，畫出新建立的線段(註明為哪兩點的中垂線)，並說明簡述流程。
## 第2題: Voronoi Diagram的應用
* 請說明The Euclidean all nearest neighbor problem為何，以及如何應用VD來解此問題？

* * **The Euclidean all nearest neighbor problem：**
為平面上n個點，找出所有點的closed neighbor(different from closest pair problem)

* * **如何應用VD來解決此問題：**
我最近的鄰居一定會和我共用VD的edge
檢查每個中垂線對應到的兩點距離，找出最小的那個為最近鄰居。
## 第3題: FFT
* 當輸入為：{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}，請說明如何應用FFT得到結果(只須說明計算過程，不用算出結果)？
## 第4題: 由Preorder與Inorder建構二元樹
* **解題思路：** 用preorder的數列當作root，之後再去inorder裡面分左右子樹，就這樣一直遞迴下去，直到葉節點(return nullptr)為止，然後先見左子樹在建右子樹。
* **程式碼：**

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    int n=inorder.size()-1;
    int preordercheck=0;
    return construct(preorder,inorder,preordercheck,0,n); 
}
    TreeNode* construct(vector<int>& preorder,vector<int>& inorder,int& preordercheck,int left,int right){
    if(left>right) return nullptr;
    int flag=left;
    while(inorder[flag]!=preorder[preordercheck])flag++;
    preordercheck++;
    TreeNode* node=new TreeNode(inorder[flag]);
    node->left=construct(preorder,inorder,preordercheck,left,flag-1);
    node->right=construct(preorder,inorder,preordercheck,flag+1,right);
    return node;
}

* **測試輸出輸入的畫面截圖：**

* **寫程式所花費的時間：** 40min
* **完成比例程度：** 自己的想法配上solution的linked list的寫法
## 第5題: 由Postorder與Inorder建構二元樹
* **解題思路：** 用postorder的最後面開始來當root，再配合inorder來區分左右子樹，就這樣一直遞迴下去，直到葉節點(return nullptr)為止，然後和上一題不同的是先見右子樹在建左子樹，基本上有了概念和上一題對linked list的練習，要自己寫這題不難。
* **程式碼：**

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    int n=inorder.size()-1;
    int postordercheck=postorder.size()-1;
    return construct(inorder,postorder,n,0,n);
}
TreeNode* construct(vector<int> inorder,vector<int> postorder,int& postordercheck,int left,int right){
    if(left>right) return nullptr;
    int flag=left; 
    while(postorder[postordercheck]!=inorder[flag]) flag++;
    postordercheck--;
    TreeNode* newNode=new TreeNode(inorder[flag]);
        
    newNode->right=construct(inorder,postorder,postordercheck,flag+1,right);
    newNode->left=construct(inorder,postorder,postordercheck,left,flag-1);
    return newNode;
}

* **測試輸出輸入的畫面截圖：**
* **寫程式所花費的時間：** 20min
* **完成比例程度：** 自己寫
## 第6題：由Pretorder與Postorder建構二元樹
* **解題思路：** 利用preorder來當root，再去找postorder來分出左右子樹，在遞迴直到nullptr為止，因為看leetcode上的solution看半天還不是很了解，所以這題有參考yt(https://www.youtube.com/watch?v=53aOi0Drp9I)的解法，寫成c++的版本比leetcode上的solution還容易理解。
* **程式碼：**

TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
    int n=preorder.size();
    return construct(preorder,postorder,0,0,n);
}
TreeNode* construct(vector<int>& preorder, vector<int>& postorder,int preoriginal,int postoriginal,int arrlen){
    if(arrlen<=0) return nullptr;
    TreeNode* node=new TreeNode(preorder[preoriginal]);
    if(arrlen==1) return node;
    int postind=postoriginal;
    while(postorder[postind]!=preorder[preoriginal+1]) postind++;
    int len=postind-postoriginal+1;
    node->left=construct(preorder,postorder,preoriginal+1,postoriginal,len);
    node->right=construct(preorder,postorder,preoriginal+len+1,postind+1,arrlen-len-1);
    return node;
}

* **測試輸出輸入的畫面截圖：**
* **寫程式所花費的時間：** 60min(包含看影片理解，跟寫出來)
* **完成比例程度：** 看yt理解後，改成c++版
## 心得：我覺得這次的作業程式題選得很漂亮，第一題其實概念就是資結有講過的，只要加上一些linked list的熟悉就可以寫出來，第二題只要第一題會寫，就一定很快就可以寫出來，第三題其實對我有點挑戰(可能是我太廢，還整天蹦重訓室上低卡)，直接看yt上的講解，理解後在自己寫，寫完發現比leetcode的c++ code還簡單易懂。