---
tags: 演算法, 110-2
---
# 演算法作業 HW8
- 本週影片只介紹兩個問題，只是第一個問題的影片長達90分鐘，第二個問題的影片長達45分鐘。大家辛苦了。
- 本週程式題都很類似，都與二元樹有關，由不同Traversal(尋訪)的結果來建構二元樹。答案有90成的相似度，因為使用遞廻，所以都很短小，不到10行。
# 觀念題 :book:
## 第1題: Voronoi Diagram
- 請畫出下圖兩個VD合併結果，畫出新建立的線段(註明為哪兩點的中垂線)，並說明簡述流程。
## 第2題: Voronoi Diagram的應用
- 請說明The Euclidean all nearest neighbor problem為何，以及如何應用VD來解此問題？
## 第3題: FFT
- 當輸入為：{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}，請說明如何應用FFT得到結果(只須說明計算過程，不用算出結果)？

## 程式題:[Divide and Conquer](https://leetcode.com/tag/divide-and-conquer/)

## 第4題: 由Preorder與Inorder建構二元樹
[Construct Binary Tree from Preorder and Inorder Traversal - LeetCode](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)
- 關於如何由Preorder與Inorder建構二元樹，可參考[Binary Tree - 演算法筆記](https://web.ntnu.edu.tw/~algo/BinaryTree.html)
- 題目給定兩個數列，分別為一個二元樹的Preorder與Inorder，請以此建構原本的二元樹。

:::success
提示：採用遞迴的寫法，先由Preorder找出root，再將二數列分為兩段，依此建構左右子樹
:::

## 第5題: 由Postorder與Inorder建構二元樹
[Construct Binary Tree from Inorder and Postorder Traversal - LeetCode](https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/)
- 題目給定兩個數列，分別為一個二元樹的Postorder與Inorder，請以此建構原本的二元樹。
:::success
提示：採用遞迴的寫法，先由Postorder找出root，再將二數列分為兩段，依此建構左右子樹
:::

## 第6題：由Pretorder與Postorder建構二元樹
[Construct Binary Tree from Preorder and Postorder Traversal - LeetCode](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/)
- 題目給定兩個數列，分別為一個二元樹的Preorder與ostorder，請以此建構原本的二元樹。
:::success
提示：可參考[Construct Full Binary Tree from given preorder and postorder traversals - GeeksforGeeks](https://www.geeksforgeeks.org/full-and-complete-binary-tree-from-given-preorder-and-postorder-traversals/)
:::

## 第7題 : 心得
- 請在以下表單填寫對本週(hw8)影片教學和程式作業的問題/收穫/適應程度/心得。
- [https://forms.gle/3FqW22n3ViN98jbZ9](https://forms.gle/3FqW22n3ViN98jbZ9)