# 演算法導論 HW8
https://hackmd.io/@wang1234/ry_AVjPHc
## 第1題: Voronoi Diagram
<font color="DarkGray" class="small">請畫出下圖兩個VD合併結果，畫出新建立的線段(註明為哪兩點的中垂線)，並說明簡述流程。</font>
| P_aP_b = P₁P₅         P_cP_d = P₂P₆ | |
| -------- | -------- |
|  | SG=P₁P₅ |
|  | SG=P₁P₄ |
|  | SG=P₃P₄ |
|  | SG=P₃P₆ |
|  | SG=P₂P₆ |
|  | |

## 第2題: Voronoi Diagram的應用
<font color="DarkGray" class="small">請說明The Euclidean all nearest neighbor problem為何？</font>
平面上n個點，找出所有點的closest neighbor
<font color="DarkGray" class="small">以及如何應用VD來解此問題？</font>
<font style="background-color:#FFFF84">&emsp;∵&emsp;VD性質：我最近的鄰居一定會與我共用VD的邊。</font>
<b>step1：</b>檢查所有的邊，提供兩點距離
<b>step2：</b>每個點依所提供的兩點距離，找出最近鄰居

## 第3題: FFT
<font color="DarkGray" class="small">當輸入為：{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}，請說明如何應用FFT得到結果(只須說明計算過程，不用算出結果)？</font>
先將{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}拆分成
奇數項{1,3,5,7,9,11,13,15}與偶數項{2,4,6,8,10,12,14,16}
，然後繼續拆分直至括號{}中剩餘兩個項目(因為兩個項目的DFT容易計算)
，再由這些包含兩個項目的DFT的計算結果，得到包含四個項目的DFT
，繼續將結果兩兩合併，即可得最終的DFT
*如下圖所示*

## 第4題: 由Preorder與Inorder建構二元樹
[105. Construct Binary Tree from Preorder and Inorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)
<font color="Black">解題思路:
> </font>

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        def tree(pre_order,in_order):
            if len(pre_order)<=0:
                return None
            root=TreeNode(pre_order[0])
            for i in range(len(in_order)):
                if(in_order[i]==pre_order[0]):
                    c=i
                    break
            root.left=tree(pre_order[1 : len(in_order[0:c])+1] , in_order[0 : c])
            root.right=tree(pre_order[len(in_order[0:c])+1 : ] , in_order[c+1 : ])
            return root
        return tree(preorder,inorder)

花30分鐘，完全靠自己

## 第5題: 由Postorder與Inorder建構二元樹
[106. Construct Binary Tree from Inorder and Postorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/)
<font color="Black">解題思路:
> 
</font>

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        def tree(post_order,in_order):
            if len(post_order)<=0:
                return None
            root=TreeNode(post_order[-1])
            for i in range(len(in_order)):
                if(in_order[i]==post_order[-1]):
                    c=i
                    break
            root.left=tree(post_order[0 : len(in_order[0:c])] , in_order[0 : c])
            root.right=tree(post_order[len(in_order[0:c]) : -1] , in_order[c+1 : ])
            return root
        return tree(postorder,inorder)

花5分鐘，完全靠自己

## 第6題：由Pretorder與Postorder建構二元樹
[889. Construct Binary Tree from Preorder and Postorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/)
<font color="Black">解題思路:
> 
> (上圖的思路是我原本的想法，但這題試了很久還是有測資沒通過
> ，程式碼是去Solutions裡找的，尚在理解中)</font>

class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not preorder or not postorder: 
            return
        root = TreeNode(preorder[0])
        if len(preorder)==1:
            return root
        mid = postorder.index(preorder[1])
        root.left = self.constructFromPrePost(preorder[1:mid+2], postorder[:mid+1])
        root.right = self.constructFromPrePost(preorder[mid+2:], postorder[mid+1:-1])
        return root

花60分鐘，抄:
[Python3 || 7 Lines Recursion || for All 3 Binary Tree Construction from 2 Traversal Problems](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/solutions/3169219/python3-7-lines-recursion-for-all-3-binary-tree-construction-from-2-traversal-problems/?languageTags=python3&topicTags=divide-and-conquer)

## 心得
觀念題寫非常久，尤其第一題很疑惑，畫了好多次，搞不懂該如何決定下一條中垂線，(不知道要替換SG中的哪一點? 以及該怎麼選新的替換點? )，後來是參考課本和別人的答案;程式題前兩題寫的很開心，但類似的思路在最後一題卻沒解成功。