# 第1題: Voronoi Diagram
總之就是劃出一條變動的中垂線段,根據2點的輪流更新最高位置而定
1,2區域的最高點連成一條
2,畫中垂,碰到連線時停下,其中最高點的那點換成該區域的次個最大點
3,重複步驟二,垂線的方向改成新連線的中垂方向,直到碰到新線時停下
4,重複至最低點結束
# 第2題: Voronoi Diagram的應用
The Euclidean all nearest neighbor problem: 給定一點p,在一個集合中找到與p距離最近的點。
如何應用VD來解此問題:選定p點,檢查所有vd邊,p點距離vd邊最短的相對點就是答案
# 第3題: FFT
W2=-1c和W4=1,W8=-1,W16=1

# 第4題: 由Preorder與Inorder建構二元樹
1小時,自己做(邊界想很久),因為是先父,然後是左,然後右,所以左子節點的根一定是當前根
在pr數列的位置+1(L+1),而要求出right的分割處則需要求當前父在inorder
位置的地方減去inorder的左邊界取得差值,而由左子位置加上差值(inorder中父到左的距離)剛好能求出right邊界,同時更新inorder的邊界繼續循環

class Solution {
public:
    vector<int>pr;
    vector<int>in;
    
    TreeNode* build(int L1, int R1, int L2, int R2){
	    if(L1==R1)return NULL;
        int val=pr[L1];
        TreeNode* root=new TreeNode(val);
          int root_i=0;
          for(int i=L2;i<R2;i++){
              if(in[i]==val){root_i=i;break;}
          }
          int left=root_i-L2;
          root->left=build(L1+1,L1+left+1,L2,root_i);
          root->right=build(left+1+L1,R1,root_i+1,R2);
          return root;
}
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
         int m=preorder.size();
        pr.assign(preorder.begin(),preorder.end());
        in.assign(inorder.begin(),inorder.end());
       
         return build(0,m,0,m);
              

    }
};


# 第5題：由Postorder與Inorder建構二元樹
1小時,自己做,原本我想說利用前一題稍微修改root和left,right那邊就行,
但我忽略了一點是前一題的root由於是pre的(父),所以可以不用留多餘的空間,
但這題是post,由於是右,左,中,所以要留出多的空間,所以root不能用post[R1],而要用post[R1-1],拿來存右節點,雖然網路上基本都是用R1,但是他們存點的方式跟我用的不太一樣,我沒像他們厲害到能輕鬆處理邊界

class Solution {
public:
    vector<int>po;
    vector<int>in;
    
    TreeNode* build(int L1, int R1, int L2, int R2){
	    if(L1==R1)return NULL;
        int val=po[R1-1];
        TreeNode* root=new TreeNode(val);
       
          int root_i=0;
          for(int i=L2;i<R2;i++){
              if(in[i]==val){root_i=i;break;}
          }
          int left=root_i-L2;
          root->left=build(L1,L1+left,L2,root_i);
          root->right=build(L1+left,R1-1,root_i+1,R2);
          return root;
}
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
         int m=postorder.size();
        po.assign(postorder.begin(),postorder.end());
        in.assign(inorder.begin(),inorder.end());
       
         return build(0,m,0,m);
              

    }
};


# 第6題：由Pretorder與Postorder建構二元樹
1小時,參考題解的,不曉得為什麼next不能在val附值的時候跟著一起,報錯說heapoverflow,改了很久換到if(L1==R1)下面就行了,也不曉得是哪裡越界
思路就是在post找出preordere的左樹(L1+1)位置,因為preorder父的下一位就是左,在postorder的位置減去L2的位置就是左樹範圍

class Solution {
public:
    vector<int>pr;
    vector<int>po;
    
    TreeNode* build(int L1, int R1, int L2, int R2){
	    if(L1>R1)return NULL;
        int val=pr[L1];
        
        TreeNode* root=new TreeNode(val);
        if(L1==R1)return root;
        int next=pr[L1+1];
          int root_i=0;
          for(int i=L2;i<R2;++i){
              if(po[i]==next){root_i=i;break;}
          }
          
          int left=root_i-L2+1;
          int right=R2-root_i-1;
          root->left=build(L1+1,L1+left,L2,root_i);
          root->right=build(R1-right+1,R1,root_i+1,root_i+right);
          return root;
}
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
         int m=preorder.size();
        pr.assign(preorder.begin(),preorder.end());
        po.assign(postorder.begin(),postorder.end());
       
         return build(0,m-1,0,m-1);
              

    }
};


# 心得
本周課堂影片老師有教一些vd演算法的基本觀念,還有可以應用的地方,像是最鄰近搜索,,同時也有教一些傅立葉轉換的公式,這東西我覺得好難,但是在影像處理等方面都很重要,而這周的程練習題也學到很多,尤其是確立分割邊界,對常常選出錯誤邊界的我來說很有挑戰性,而我覺得最難的一題可能就是中序和後序的生成了,因為遞歸左子的範圍跟右子的範圍很嚴格