# **演算法作業 HW10**
<font size=5>**1. 01背包問題**</font>
---
* 已知有六個物品，其價值和重量如下，背包重量限制為34。
* 仿照課本以tree search來解。
* 請將下圖中的框框中，填入其upper bound與lower bound
Ans：

<font size=5>**2. A * 解multi-stage shortest path problem**</font>
---
* 請使用A* 找出S到T的最短路徑。請畫出樹狀圖，並標示各點的cost，並註明哪裏分枝不用再繼續尋找了。
Ans：

<font size=5>**3. Channel Routing Problem**</font>
---
* 請使用A* 解Channel Routing Problem。
* 本題將原本題目的net 7移除，只剩下7個nets，請找出最少track的安排方式。
Ans：
**{ 1, 8 }, { 2, 3 }, { 5 }, { 4, 6 }**

<font size=6>**Breadth-First Search**</font>
---

<font size=5>**4. 合併二元樹**</font>
---
[Merge Two Binary Trees - LeetCode](https://leetcode.com/problems/merge-two-binary-trees/)
若節點都存在才需要合併。
如果其中一棵樹沒有節點，就把另一棵樹的節點接上去就好。
參考網上答案，完成時間，一分鐘。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        //建一個新的樹比較麻煩，所以直接合併到其中一棵樹上
        //若有其中一棵樹沒有此位置的節點，就直接把有的接上去就好
        if(!root1)
          return root2;
        if(!root2)
          return root1;
        //兩棵樹都有此位置的節點，將值加起來合併
        root1->val+=root2->val;
        root1->left = mergeTrees(root1->left ,root2->left);
        root1->right = mergeTrees(root1->right ,root2->right);
        
        return root1;
    }
};


<font size=5>**5. 最深葉子的最低共同祖先**</font>
---
[Lowest Common Ancestor of Deepest Leaves - LeetCode](https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/)
用BFS下去探訪，紀錄每個點的路徑。
得出最深葉節點後，找出每個最深葉節點路徑的最長共同前綴。
該路徑得出的點就是最低共同祖先。
完全靠自己，完成時間：20分鐘。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //最長共同字串前綴
    string LCP(vector<string>&v)
    {
        string lcp="",shortest=v[0];
        //取出最短字串
        for(int i=1;i<v.size();++i)
        {
            if(v[i].length()<shortest.length())
                shortest=v[i];
        }
        //比較並更新最長共同前綴
        for(int i=0;i<shortest.length();++i)
        {
            for(auto s:v)
            {
                if(s[i]!=shortest[i])
                    return lcp;
            }
            lcp+=shortest[i];
        }
        return lcp;
    }
    TreeNode* lcaDeepestLeaves(TreeNode* root) {
        //在BFS時用map{點,路徑}去紀錄每個點
        //最後得出最深葉子點所有路徑的共同前綴
        //前綴路徑得出的點就是共同祖先
        unordered_map<TreeNode*,string>m;
        queue<TreeNode*> q, temp;
        q.push(root);
        m[root]="";
        while(!q.empty())
        {
            temp = q;
            int n = q.size();
            for(int i=0;i<n;++i)
            {
                TreeNode *r = q.front();
                q.pop();
                string s=m[r];
                if(r->left)
                {
                    q.push(r->left);
                    m[r->left]=s+"0";
                }  
                if(r->right)
                {
                    q.push(r->right);
                    m[r->right]=s+"1";
                }  
            }
        }
        //此時temp裡是最深葉節點
        if(temp.size()==1)
            return temp.front();
        vector<string>v;
        //將所有最深葉節點路徑放入vector
        while(!temp.empty())
        {
            v.push_back(m[temp.front()]);
            temp.pop();
        }
        //得到最長共同前綴
        string s=LCP(v);
        //根據路徑得出最低共同祖先
        for(auto c :s)
        {
            if(c=='0')
                root=root->left;
            else
                root=root->right;
        }
        return root;
    }
};


<font size=5>**6. 本周心得**</font>
---
這次的題目也不會到很複雜，不過花比較多時間在想優化的方法。

---
若有錯誤歡迎指正