297. Serialize and Deserialize Binary Tree

題目網址：https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/

題意：Serialize 是將資料結構轉換成一系列的 bit, 進而將其儲存在 file 或 buffer 中, 也可以透過網路傳輸到另一台電腦, 並重構得到原資料。

設計一個 BT 的 Serialize 和 Deserialize 功能, 讓一個 BT 可透過 Serialize 轉換成 string, 並透過 Deserialize 重構回 BT。

Solution 1：

想法：利用 DFS, 用 preorder 遍歷 BT, 並加入到 string 中, 記得 val 之間要用 ',' 隔開, 且用 '#' 代表 nullptr

idx 的 left child 必為 idx + 1

當 decodeDFS(nodes, idx) 做完後, idx 會指向下一個 preorder 位置

所以當 root->left = decodeDFS(nodes, idx) 做完後, idx 會指向 root->right 的位置

e.g. root = [1,2,3], 可得到 nodes = ["1","2","#","#","3","#","#"]

idx = 0 時, 呼叫 encodeDFS(nodes, 0)

nodes[0]->left :

會先呼叫 encodeDFS(nodes, 1)

首先會先呼叫 encodeDFS(nodes, 2)

由於 nodes[2] 為 "#", idx + 1 = 3, 並返回 nullptr
➔ nodes[1] 得到 left child = nullptr

接著呼叫 encodeDFS(nodes, 3), 由於 nodes[3] 為 "#", idx + 1 = 4, 並返回 nullptr
➔ nodes[1] 得到 right child = nullptr

然後 encodeDFS(nodes, 1) 返回 nodes[1] ➔ nodes[0] 得到其 left child

nodes[0]->right :

接著, 呼叫 encodeDFS(nodes, 4)

首先會先呼叫 encodeDFS(nodes, 5)

由於 nodes[5] 為 "#", idx + 1 = 6, 並返回 nullptr
➔ nodes[4] 得到 left child = nullptr

接著呼叫 encodeDFS(nodes, 6), 由於 nodes[6] 為 "#", idx + 1 = 7, 並返回 nullptr
➔ nodes[4] 得到 right child = nullptr

然後 encodeDFS(nodes, 4) 返回 nodes[4] ➔ nodes[0] 得到其 right child

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res;
        encodeDFS(root, res);
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        const int n = data.size();
        int idx = 0;
        vector<TreeNode*> nodes;

        // 先將 string 中每個 val 拆出來, 並轉換成 TreeNode
        // 然後再將 TreeNode* push 到 nodes 中
        for (int i = 0; i < n; ++i) {
            int j = i; // 從 i 開始往後找

            // j 指向 i 後面第一個 ',' 的位置
            while (j < n && data[j] != ',') {
                ++j;
            }

            // 取出兩個 ',' 之間的 substring
            const string str = data.substr(i, j - i);
            if (str == "#") {
                nodes.emplace_back(nullptr);
            } else {
                const int val = stoi(str); // string 轉換成 int
                nodes.emplace_back(new TreeNode(val));
            }

            i = j; // 讓 i 下一輪從 ',' 的下一個 idx 開始
        }

        return decodeDFS(nodes, idx);
    }

private:
    // preorder 遍歷 BT
    void encodeDFS(TreeNode* root, string& res){
        if (!root) {
            res += "#,";
            return;
        }

        res += (to_string(root->val) + ","); // int 轉換成 string
        encodeDFS(root->left, res);
        encodeDFS(root->right, res);
    }

    // 將 preorder 轉換成 BT
    TreeNode* decodeDFS(vector<TreeNode*>& nodes, int& idx){
        if (!nodes[idx]) {
            ++idx;
            return nullptr;
        }

        const auto root = nodes[idx];
        ++idx; // idx 指向 root->left 的位置
        root->left = decodeDFS(nodes, idx); // 做完後, idx 會指向 root->right 的位置
        root->right = decodeDFS(nodes, idx);

        return root;
    }
};

time：$O(n)$ ➔ 遍歷 BT
space：$O(n)$ ➔ nodes

Solution 2：

想法：利用 BFS, 用 level-order 遍歷 BT, 並建立 string。然後用 i 來遍歷 parent node, 而 j 用來指向 nodes[i] 的 child node

e.g. root = [1,2,3], 可得到 nodes = ["1","2","3","#","#","#","#"]

i = 0 時, j = 1 ➔ nodes[0] 得到 nodes[1]、nodes[2] 分別為其 left、right child

j += 2 指向下一個不為 nullptr 的 nodes[i] 之 left child

i += 1 移動到下一個 parent node

i = 1 時, j = 3 ➔ nodes[1] 得到 nodes[3]、nodes[4] 分別為其 left、right child

j += 2 指向下一個不為 nullptr 的 nodes[i] 之 left child

i += 1 移動到下一個 parent node

i = 3 時, j = 5 ➔ nodes[3] 得到 nodes[5]、nodes[6] 分別為其 left、right child

j += 2 指向下一個不為 nullptr 的 nodes[i] 之 left child

i += 1 移動到下一個 parent node

i = 4 時, j = 7 ➔ 跳出迴圈

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res;
        queue<TreeNode*> q;
        q.emplace(root);

        // bfs
        while (!q.empty()) {
            const auto node = q.front();
            q.pop();

            if (!node) {
                res += "#,";
            } else {
                res += (to_string(node->val) + ","); // int 轉換成 string
                q.emplace(node->left); // push left child into q
                q.emplace(node->right); // push right child into q
            }
        }
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        const int n = data.size();
        vector<TreeNode*> nodes;

        // 先將 string 中每個 val 拆出來, 並轉換成 TreeNode
        // 然後再將 TreeNode* push 到 nodes 中
        for (int i = 0; i < n; ++i) {
            int j = i; // 從 i 開始往後找

            // j 指向 i 後面第一個 ',' 的位置
            while (j < n && data[j] != ',') {
                ++j;
            }

            // 取出兩個 ',' 之間的 substring
            const string str = data.substr(i, j - i);
            if (str == "#") {
                nodes.emplace_back(nullptr);
            } else {
                const int val = stoi(str); // string 轉換成 int
                nodes.emplace_back(new TreeNode(val));
            }

            i = j; // 讓 i 下一輪從 ',' 的下一個 idx 開始
        }

        int i = 0, j = 1; // i 代表 parent idx, j、j + 1 分別代表 left、right child
        while (j < nodes.size()) {
            if (nodes[i]) {
                nodes[i]->left = nodes[j];
                nodes[i]->right = nodes[j+1];
                j += 2; // 指向下一個 parent 的 child
            }
            i += 1;
        }

        return nodes[0];
    }
};

time：$O(n)$ ➔ 遍歷 BT
space：$O(n)$ ➔ nodes