演算法作業 HW8

觀念題

第1題: Voronoi Diagram

第2題: Voronoi Diagram的應用

第3題: FFT

程式題

第4題: 由Preorder與Inorder建構二元樹

通過畫面截圖

程式碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 建立一個哈希表，用來存儲中序遍歷序列中每個節點對應的索引
        unordered_map<int, int> inorder_map;
        for (int i = 0; i < inorder.size(); i++) {
            inorder_map[inorder[i]] = i;
        }
        
        // 調用遞歸函數構建二叉樹
        return buildTreeHelper(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1, inorder_map);
    }
    
    // 遞歸構建二叉樹
    TreeNode* buildTreeHelper(vector<int>& preorder, int pre_start, int pre_end,
                              vector<int>& inorder, int in_start, int in_end,
                              unordered_map<int, int>& inorder_map) {
        // 如果前序遍歷序列中的左指針大於右指針，則返回空指針
        if (pre_start > pre_end) {
            return nullptr;
        }
        // 建立一個新節點作為樹的根節點
        TreeNode* root = new TreeNode(preorder[pre_start]);
        // 在中序遍歷序列中找到樹的根節點的索引
        int root_index = inorder_map[root->val];
        // 左子樹的節點個數
        int left_tree_size = root_index - in_start;
        // 遞歸構建左子樹和右子樹
        root->left = buildTreeHelper(preorder, pre_start+1, pre_start+left_tree_size,
                                      inorder, in_start, root_index-1, inorder_map);
        root->right = buildTreeHelper(preorder, pre_start+left_tree_size+1, pre_end,
                                       inorder, root_index+1, in_end, inorder_map);
        
        return root;
    }
};

解題思路

先建立一個哈希表來儲存inorder中每個節點值對應的索引，然後用一個輔助函數來做BST。
在輔助函數中，先判斷遞歸終止條件。
如果pre_start大於pre_end，則返回空指針。
否則用Preorder去構建根節點。
然後在inorder中查找根節點的位置，並計算左子樹的節點數。
最後，我們遞歸構建left tree和right tree，
並將它們分別作為當前節點的左子節點和右子節點。
最後返回根節點。

花費時間

半小時

自己完成的比例

參考網路上的答案，尚未理解明白

第5題: 由Postorder與Inorder建構二元樹

通過畫面截圖

程式碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        unordered_map<int, int> inorder_map;
        for (int i = 0; i < inorder.size(); i++) {
            inorder_map[inorder[i]] = i;
        }
        
        return buildTreeHelper(inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1, inorder_map);
    }
    
    TreeNode* buildTreeHelper(vector<int>& inorder, int in_start, int in_end, vector<int>& postorder, int post_start, int post_end, unordered_map<int, int>& inorder_map) {
        if (in_start > in_end) {
            return nullptr;
        }
        
        TreeNode* root = new TreeNode(postorder[post_end]);
        int root_index = inorder_map[root->val];
        int left_tree_size = root_index - in_start;
        
        root->left = buildTreeHelper(inorder, in_start, root_index-1, postorder, post_start, post_start+left_tree_size-1, inorder_map);
        root->right = buildTreeHelper(inorder, root_index+1, in_end, postorder, post_start+left_tree_size, post_end-1, inorder_map);
        
        return root;
    }
};

解題思路

和前一個做法相似，先建立一個哈希表來儲存inorder中每個節點值對應的索引。
然後用一個輔助函數來進行BST。
在輔助函數中先判斷遞歸終止條件。
如果in_start大於in_end，則返回空指針。
否則，我們根據postorder結果構建根節點。
然後在中序遍歷中查找根節點的位置，並計算left tree的節點數。
最後，我們遞歸構建left tree和right tree，
並將它們分別作為當前節點的左子節點和右子節點。最後返回根節點即可。

花費時間

二十分鐘

自己完成的比例

參考網路上的答案，尚未理解明白

第6題：由Pretorder與Postorder建構二元樹

通過畫面截圖

程式碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
        return buildTreeHelper(pre, 0, pre.size()-1, post, 0, post.size()-1);
    }
    
    TreeNode* buildTreeHelper(vector<int>& pre, int pre_start, int pre_end, vector<int>& post, int post_start, int post_end) {
        if (pre_start > pre_end) {
            return nullptr;
        }
        
        TreeNode* root = new TreeNode(pre[pre_start]);
        
        if (pre_start == pre_end) {
            return root;
        }
        
        int left_root_val = pre[pre_start+1];
        int left_root_index = -1;
        for (int i = post_start; i <= post_end; i++) {
            if (post[i] == left_root_val) {
                left_root_index = i;
                break;
            }
        }
        
        int left_tree_size = left_root_index - post_start + 1;
        
        root->left = buildTreeHelper(pre, pre_start+1, pre_start+left_tree_size, post, post_start, left_root_index);
        root->right = buildTreeHelper(pre, pre_start+left_tree_size+1, pre_end, post, left_root_index+1, post_end-1);
        
        return root;
    }
};

解題思路

先根據preorder結果構建根節點。然後在postorder中查找左子樹的根節點。根據preorder中根節點後面的節點可以得到left tree的節點數量。最後，我們遞歸構建left tree和right tree，並將它們分別作為當前節點的左子節點和右子節點。最後返回根節點。

花費時間

約一小時

自己完成的比例

參考網路上的答案，尚未理解明白

心得

這次的影片長度真的很長，而且是本學期以來最難的一次，稍加難懂，但是回放一兩次之後都會懂，然而第一題的解題，我覺得題目給的點有不夠精確的問題，導致我在畫圖的時候花了約半小時。程式題的部分，幸好與這次的觀念題沒有相關，解題解得比較快，若是程式題也與觀念題一樣難，我覺得恐怕以我的能力很難解出來。