# 演算法導論 HW10
https://hackmd.io/@wang1234/HkWbPrqI5
## 第1題: 01背包問題

## 第2題: A* 解multi-stage shortest path problem
<font color="DarkGray" class="small">請使用A* 找出S到T的最短路徑。請畫出樹狀圖，並標示各點的cost，並註明哪裏分枝不用再繼續尋找了。</font>
最短路徑: S → C → F → T

## 第3題: Channel Routing Problem

<font color="DarkGray" class="small">請使用A* 解Channel Routing Problem。
請找出最少track的安排方式。</font>
|  |  |
| -------- | -------- |

最少track的安排方式: {8,1} → {3,2} → {5} → {4,6}

## 第4題: 合併二元樹
[617. Merge Two Binary Trees](https://leetcode.com/problems/merge-two-binary-trees/)
<font color="Black">解題思路:
> 當tree_1和tree_2都已沒有節點(已達終端),return None;
> 或者tree_1和tree_2的只剩其一有節點,將節點的值用來建合併樹的節點,然後在遞迴中沒有節點的樹就傳None;
> 若是tree_1和tree_2都還存在節點,合併樹的節點值為兩節點值的和</font>

class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        def merge(tree_1,tree_2):
            if not tree_1 and not tree_2:
                return None
            if not tree_1:
                m=TreeNode(tree_2.val)
                m.left= merge(None , tree_2.left)
                m.right= merge(None , tree_2.right)
            elif not tree_2:
                m=TreeNode(tree_1.val)
                m.left= merge(tree_1.left , None)
                m.right= merge(tree_1.right , None)
            else: 
                m=TreeNode(tree_1.val + tree_2.val)
                m.left= merge(tree_1.left , tree_2.left)
                m.right= merge(tree_1.right , tree_2.right)
            return m
        return merge(root1,root2)

花30分鐘，完全靠自己

## 第5題: 最深葉子的最低共同祖先
[1123. Lowest Common Ancestor of Deepest Leaves](https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/)
<font color="Black">解題思路:
> 先用DFS將從根部到終端的所有路徑羅列出來,每條路徑都作為一個list,
> 在這些路徑的list中找長度最長的,即為到達最深葉子的路徑,然後再從list末尾去找所有最長list的共同元素,即最低共同祖先
> 最後再次歷遍原本的二元樹,在最低共同祖先出現的時候,將預先令好的一個TreeNode的指標指向這位祖先,最後返回TreeNode的指標</font>

class Solution:
    def lcaDeepestLeaves(self, root:Optional[TreeNode])->Optional[TreeNode]:
        dfs_ans = []  #放dfs的結果     
        def dfs(node,path):
            path.append(node.val)
            if not node.left and not node.right:
                dfs_ans.append(list(path))  #一定要list,否則加入的path是指標,會繼續被改變
                return
            if node.left:
                dfs(node.left, list(path))
            if node.right:
                dfs(node.right, list(path))
            return
        dfs(root, [])
        #print(dfs_ans)
        longest=0
        for i in dfs_ans:
            if len(i)>longest:
                longest=len(i)
        ans=[]
        for i in dfs_ans:
            if len(i)==longest:
                ans.append(i)
        #print(ans)
        if len(ans)==1:
            tree=TreeNode(ans[0][-1])
            return tree

        def find(A):
            for i in range(len(A[0])-1,-1,-1):
                x=A[0][i]
                for j in range(1,len(A)):
                    if x==ans[j][i]:              
                        if j==len(A)-1:      #找到共同點
                            return ans[0][i]
        found=find(ans)
        #print(found)
        tree=TreeNode()
        def cut(node,x,tree):
            if not node:
                return None
            #print(node.val)
            if node.val==x:
                tree.left=node
            cut(node.left,x,tree)
            cut(node.right,x,tree)
        cut(root,found,tree)
        return tree.left

花3小時，參考DFS的程式:
[BFS vs DFS for Binary Tree - GeeksforGeeks](https://www.geeksforgeeks.org/bfs-vs-dfs-binary-tree/)
[python || simple solution || recursive dfs](https://leetcode.com/problems/binary-tree-paths/solutions/2840036/python-simple-solution-recursive-dfs/)

## 心得
第三題的Channel Routing Problem，可能因為做法比較繁複，寫得很混亂，寫出來後再檢查、回顧時，發現好像{3,1} → {8,2} → {5} → {4,6}也符合最少track的安排方式?