演算法作業 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

第4題: 由Preorder與Inorder建構二元樹

Construct Binary Tree from Preorder and Inorder Traversal - LeetCode

• 關於如何由Preorder與Inorder建構二元樹，可參考Binary Tree - 演算法筆記
• 題目給定兩個數列，分別為一個二元樹的Preorder與Inorder，請以此建構原本的二元樹。

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

第5題: 由Postorder與Inorder建構二元樹

Construct Binary Tree from Inorder and Postorder Traversal - LeetCode

• 題目給定兩個數列，分別為一個二元樹的Postorder與Inorder，請以此建構原本的二元樹。

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

第6題：由Pretorder與Postorder建構二元樹

Construct Binary Tree from Preorder and Postorder Traversal - LeetCode

• 題目給定兩個數列，分別為一個二元樹的Preorder與ostorder，請以此建構原本的二元樹。

提示：可參考Construct Full Binary Tree from given preorder and postorder traversals - GeeksforGeeks

第7題 : 心得

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