# 演算法第十一周

## 觀念題
### 第1題: 01背包問題
- 已知有六個物品，其價值和重量如下，背包重量限制為34。
- 仿照課本以tree search來解。
- 請將下圖中的框框中，填入其upper bound與lower bound
### 第2題: A* 解multi-stage shortest path problem
- 請使用A* 找出S到T的最短路徑。請畫出樹狀圖，並標示各點的cost，並註明哪裏分枝不用再繼續尋找了。
- 樹狀圖
> 最短路徑: S->C->F->T
### 第3題: Channel Routing Problem
- 請使用A* 解Channel Routing Problem。
- 本題將原本題目的net 7移除，只剩下7個nets，請找出最少track的安排方式。
- 將限制畫成圖
- 那我們經由A-star algorithm搜尋
- 因此知道我們可以這樣分配track
> 故最小track數為4
## 實作題
### 第4題: 合併二元樹
[leetcode 617](https://leetcode.com/problems/merge-two-binary-trees/description/)
- 程式碼
- BFS
:::spoiler C++

        typedef TreeNode* nodePtr;
        class Solution {
        public:
            TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
                typedef pair<nodePtr,nodePtr> PAIR;
                if (!root1 && !root2) return NULL;
                if (!root1 || !root2) return root1?root1:root2;

                queue<PAIR> bfs;
                bfs.push(PAIR(root1,root2));

                while (!bfs.empty()){
                    nodePtr p1 = bfs.front().first;
                    nodePtr p2 = bfs.front().second;
                    bfs.pop();

                    p1->val += p2->val;

                    if (!p1->left && p2->left) p1->left = p2->left;
                    else if (p1->left && p2->left) bfs.push(PAIR(p1->left,p2->left));

                    if (!p1->right && p2->right) p1->right= p2->right;
                    else if (p1->right && p2->right) bfs.push(PAIR(p1->right,p2->right));      
                }
                return root1;
            }
        };

:::
- DFS
:::spoiler C++

        class Solution {
        public:
            TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
                if (!root1 || !root2) return root1?root1:root2;
                typedef TreeNode* nodePtr;
                function<nodePtr(nodePtr,nodePtr)> dfs = [&](nodePtr root1,nodePtr root2){
                    root1->val = root1->val + root2->val;

                    if (root1->left && root2->left) 
                        root1->left = dfs(root1->left,root2->left);
                    else
                        root1->left = root1->left?root1->left:root2->left;

                    if (root1->right && root2->right) 
                        root1->right = dfs(root1->right,root2->right);
                    else
                        root1->right = root1->right?root1->right:root2->right;

                    return root1;
                };
                return dfs(root1,root2);
            }
        };

:::
- 執行結果
- 完成程度: 完全靠自己
- 花費時間: 30分鐘
- 思路
- 想法很簡單，直接一層一層加 => BFS
- 因此我在這邊把Tree1, Tree2相對的節點塞入queue裡面
- 在這邊我使用了

            typedef pair<nodePtr,nodePtr> PAIR;

- 寫起來比較方便，而且可讀性也比較高
- 有個問題，如果小孩是空 => 那我在塞入前要檢查小孩是不是空，如果是，我直接拿另外一個人的移花接木就好
### 第5題: 最深葉子的最低共同祖先
[leetcode 1123](https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/description/)
- 程式碼
:::spoiler C++

    typedef TreeNode* nodePtr;
    class Solution {
    private:
        nodePtr ans;
        int maxDepth;
    public:
        TreeNode* lcaDeepestLeaves(TreeNode* root) {
            depth(root,0);
            return ans;
        }
    private:
        int depth(nodePtr root, int d){
            if (!root) return 0;

            // if left is null => left's depth is same as root
            // so is right
            int left  = d;
            int right = d;

            if (root -> left)  left  = depth(root->left,d+1);
            if (root -> right) right = depth(root->right,d+1);

            maxDepth = max(maxDepth,d);
            if (maxDepth == left && maxDepth == right) ans = root;

            return max(left,right);
        }
    };

:::
- 執行結果
- 完成程度: 有參考他人
- [ref 1](https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/solutions/4751397/beats-90/)
- [ref 2](https://www.youtube.com/watch?v=DUXvcoEZJqw&ab_channel=HuifengGuan)
- 花費時間: 1小時
- 思路
- 這題是大魔王吧@@
- 在這裡我們可以邊做DFS邊算深度，並每一次更新最深值
- 然後每個節點都會回傳其小孩的最深深度，如果左邊小孩深度與右邊小孩深度都是一樣的且深度相同
- 記錄起來，最後一個就是我要的了(因為程式碼中需討論root的兩小孩深度是否相同=>相同代表剛剛的祖先需要重新改過)
### 第6題: 二元樹修剪
[leetcode 814](https://leetcode.com/problems/binary-tree-pruning/description/)
- 程式碼
:::spoiler C++

    class Solution {
    public:
        TreeNode* pruneTree(TreeNode* root) {
            bool r = contain0(root);
            if (r) root = NULL;
            return root;
        }
    private:
        bool contain0(TreeNode* root){
            if (!root) return true;

            bool left  = contain0(root->left);
            bool right = contain0(root->right);

            if (left)  root -> left  = NULL;
            if (right) root -> right = NULL;

            return left && right && root->val == 0;
        }
    };

:::
- 執行結果
- 完成程度: 靠自己
- 花費時間: 30分鐘
- 思路
- 這題我有點引入分治法的概念
- Divide
- 將節點都拆成只剩下一個
- 只剩下一個時就回傳是不是0
- Merge
- 當合成時如果左or右包含零 => 直接修剪
- 然後回傳時要考慮左右中是不是都是零
## 心得
這周老師教了背包問題與A-star Algorithm，最讓我印象深刻的是背包問題可以化成樹的搜尋方式，其實蠻酷的。

然後這周程式題又是樹，但我覺得也有一點補足我之前大一在DFS與BFS的盲點(好我希望QAQ)，然後我好喜歡二元樹修剪(leetcode 814)那題，我覺得那題蠻好玩的(只是測試資料好機車)，我後來透過回傳該子樹是否都是為0來決定是否修剪。