# 演算法導論 HW9
https://hackmd.io/@wang1234/BJh_PEZLc
## 第1題: 最短路徑
<font color="DarkGray" class="small">請使用Branch-and-Bound找出下圖中，S到T的最短路徑。請畫出Branch-and-Bound圖，並標示各點的cost，以及被bound住的地方。</font>
最佳解為: S → C → F → T , cost=9

## 第2題: Personnel Assignment Problem
<font color="DarkGray" class="small">請使用Branch-and-Bound找出最少費用的人員工作分配。</font>
最佳解為: P1做J2 → P2做J5 → P3做J1 → P4做J3 → P5做J4 , 費用=70

## 第3題: Traveling Salesperson Optimization Problem
<font color="DarkGray" class="small">請計算出圖中每個紅框的lower bound，並列出reduced matrix。</font>
 lower bound=96

## 第4題: 左右反轉二元樹
[226. Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/)
<font color="Black">解題思路:
> 新建一棵樹
> 將在原本的樹中,屬於右子樹的部分,派給新建的樹的左子樹
> 在原本的樹中,屬於左子樹的部分,則派給新建的樹的右子樹
> 這棵新的樹即為題目所要求的反轉樹</font>

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def tree(original):
            if not original:
                return None
            reverse=TreeNode(original.val)
            reverse.left=tree(original.right)
            reverse.right=tree(original.left)
            return reverse
        return tree(root)

花30分鐘，完全靠自己

## 第5題:
[230. Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst/)
<font color="Black">解題思路:
> </font>

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        def tree_to_list(root):
            if not root:
                return []
            return tree_to_list(root.left)+[root.val]+tree_to_list(root.right) 
        tree_list = tree_to_list(root)
        return tree_list[k-1]

花60分鐘，參考:
[Python | Easy Recursive Solution | O(n) | Beats 96.85%](https://leetcode.com/problems/kth-smallest-element-in-a-bst/solutions/2733644/python-easy-recursive-solution-o-n-beats-96-85/?languageTags=python3)

## 心得
程式的最後一題雖然知道二元搜尋樹的特性，卻沒有成功做出來，因為在取節點插入list的這段處理，沒有找到正確的方法