297. 二叉樹的序列化與反序列化

思路

根據題目要求，要能將一個二叉樹變成字串，然後再變回去，而且是唯一的。
所以按照前序（或後序）遍歷，將特定符號去代表「nullptr」與「分隔」。
範例程式碼當中是用#以及空格去表示這兩個東西。

1. dfs

class Codec {
public:
    string serialize(TreeNode* root) {
        string res; 
        auto dfs = [&](this auto&& dfs, TreeNode* node) -> void {
            if(!node) {
                res += "# ";
            } 
            else {
                res += to_string(node->val) + " ";
                dfs(node->left);
                dfs(node->right);
            }
        };
        dfs(root);
        return res;
    }
    TreeNode* deserialize(string data) {
        auto decode = [&](this auto&&decode, stringstream& ss) -> TreeNode* {
            string val;
            if(!(ss >> val) || val == "#") return nullptr;
            TreeNode* node = new TreeNode(stoi(val));
            node->left = decode(ss);
            node->right = decode(ss);
            return node;
        };
        stringstream ss(data);
        return decode(ss);
    }
};

按層序列化與反序列化

另外一種方式是按照「層」去序列化與反序列化，不按照前序或後序，而是一層層的去遍歷。
用queue來得到每一層的內容。
需要注意的是，即使左右節點是空的，也能加入到queue當中，因為空節點要轉換為#。
因此在讀取時需要判斷當前節點是否為空，若是空的，就不能將左右節點加入，
因為根本就不存在，會出錯。

怎麼序列化，就怎麼反序列化，根據讀到的字串去建立根結點，
隨後用queue建出剩下的節點，假如建出來的節點不為空，就加入到隊列去做後續的擴展。

2. 按層序列化與反序列化

class Codec {
public:
    string serialize(TreeNode* root) {
        if(!root) return ""; // 避免 root 為空時, 回傳 "#"
        string res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            int size = q.size();
            while(size--) {
                TreeNode* cur = q.front();
                q.pop();
                if(!cur) {
                    res += "# ";
                }
                else { // cur 非空才去加入左右兩端
                    res += to_string(cur->val) + " ";
                    q.push(cur->left);
                    q.push(cur->right);
                }
            }
        }
        return res;
    }
    TreeNode* generate(string s) {
        if(s == "#") return nullptr;
        return new TreeNode(stoi(s));
    }
    TreeNode* deserialize(string data) {
        if(data == "") return nullptr;
        stringstream ss(data);
        string s;
        
        ss >> s; 
        TreeNode* root = generate(s);
        
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            TreeNode* cur = q.front();
            q.pop();
            ss >> s; cur->left = generate(s);
            ss >> s; cur->right = generate(s);
            if(cur->left) q.push(cur->left);
            if(cur->right) q.push(cur->right);
        }
        return root;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(H)$，$H$ 是樹的高度。