# 演算法第十周
## 觀念題
### 第1題: 最短路徑
- 圖示
> 答案為9，路徑是SCFT
### 第2題: Personnel Assignment Problem
- 圖示

> 最少費用: 67，當指派j2 j5 j1 j3 j4給P1~P5

### 第3題: Traveling Salesperson Optimization Problem
- 圖示

## 程式題
### 第4題: 左右反轉二元樹
[leetcode 226](https://leetcode.com/problems/invert-binary-tree/description/)
- 程式碼
:::spoiler C++

    typedef TreeNode* nodePtr;
    class Solution {
    public:
        TreeNode* invertTree(TreeNode* root) {
            if (!root) return NULL;

            nodePtr node = new TreeNode(root -> val);

            node->left  = invertTree(root->right);
            node->right = invertTree(root->left);

            return node;
        }
    };

:::
- 執行結果
~~講個笑話，我情人節有寫過這題。。。~~
- 完成程度: 靠自己
- 花費時間: 10分鐘
- 思路
- 這題的目的要把二元樹反轉
- 所以我們只要弄出一個新樹，然後用分治法把她拆成兩個子問題
- Divide，分成左節點與右節點兩個部分，直到無法分割
- Mergr，將原本的左節點接到目標右節點上，反之右節點
- 最後就可以得到反轉後的二元樹了

### 第5題: 第k小節點
[leetcode 230](https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/)
- 程式碼
:::spoiler C++

    typedef TreeNode* nodePtr;
    class Solution {
    private:
        vector<int> trversal;
    public:
        int kthSmallest(TreeNode* root, int k) {
            inorder(root);
            return trversal[k-1];
        }
    private:
        void inorder(nodePtr root){
            if (!root) return;

            inorder(root->left);
            trversal.push_back(root->val);
            inorder(root->right);
        }
    };

:::
- 執行結果
- 完成程度: 靠自己
- 花費時間: 10分鐘
- 思路
- 思考一下二元樹特性
- 左子樹<中節點<右子樹
- 也因此，當我們用inorder treversal時，其實得到的順序就是升序的數列，可喜可樂 :clap:
- 知道了二元樹特性後，我做的其實就是先把inorder得到數列，再找第k個數列就是所求了!
> 盧教授: 各位同學資料結構真的很重要，不管是以後高考普考三等研究所考試都會考到

### 第6題: 最深葉子和
[leetcode 1320](https://leetcode.com/problems/deepest-leaves-sum/description/)
- 程式碼
:::spoiler C++

    typedef TreeNode* nodePtr;
    struct PAIR{
        int depth;
        nodePtr val;
        PAIR(int d,nodePtr v){
            depth = d;
            val = v;
        }
    };

    class Solution {
    private:
        int ans = 0;
        int treeDepth;
    public:
        int deepestLeavesSum(TreeNode* root) {
            treeDepth = depth(root);
            slove(root);
            return ans;
        }
    private:
        int depth(nodePtr root){
            if (!root) return 0;

            int leftSubTreeDepth = depth(root->left);
            int rightSubTreeDepth = depth(root->right);

            return max(leftSubTreeDepth,rightSubTreeDepth)+1;
        }
        void slove(nodePtr root){
            queue<PAIR> bfs;
            bfs.push(PAIR(1,root));
            while (!bfs.empty()){
                PAIR curr = bfs.front();
                bfs.pop();
                int d = curr.depth;
                nodePtr val = curr.val;
                if (d == treeDepth) ans += val -> val;
                else{
                    if (val->left) bfs.push(PAIR(d+1,val->left));
                    if (val->right) bfs.push(PAIR(d+1,val->right));
                }
            }
        }
    };

:::
- 執行結果
- 完成程度: 靠自己
- 花費時間: 50分鐘
- 思路
- 這題看到當初有愣住一下，後來仔細想我可以將問題拆分一下
- 先求出樹的深度
- 再找出最深樹的總和
- 但是要怎麼知道該節點的深度呢?
- 我在這邊使用了一個PAIR

            struct PAIR{
                int depth;
                nodePtr val;
                PAIR(int d,nodePtr v){
                    depth = d;
                    val = v;
                }
            };

- 但後來想想為甚麼我不要這樣==

            typedef pair<int,nodePtr> PAIR;

- 有了這個就可以繼續了，首先我先用`depth()`探測樹的深度
- 最後跑BFS時只要每次dequeue看高度是不是要的深度，如果不是那就繼續看左右節點，並把他們深度++即可，真方便

## 心得
這周學了搜尋策略，有好多種，DFS、BFS、Best First Search...資料結構中當初最讓我頭痛的DFS、BFS也在這裡，想到這個頭又痛。

這周程式題感覺和D&C的很像，有一些題目要將問題拆成一堆子問題，然後使用遞迴求解。希望我遞迴能更加精進:)。