LeetCode 297. 二叉树的序列化与反序列化

题目描述

297. 二叉树的序列化与反序列化

解法：

我们知道要唯一确定一棵二叉树，要么是前序 + 中序，要么是中序 + 后序。

但是，在这道题中前序遍历的结果记录了空指针的信息，那么就可以序列化结果唯一确定一棵二叉树

下面展示通过前序遍历序列化和反序列二叉树，同理我们也可以通过后序、中序遍历来序列化二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string str = "";
        serialize_helper(root, str);
        return str;
    }
    void serialize_helper(TreeNode* root, string& str)
    {
        if (root == nullptr) 
        {
            str += "None,";
            return;
        }
        str += to_string(root->val) + ',';
        serialize_helper(root->left, str);
        serialize_helper(root->right, str);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        list<string> nodes;
        string str;
        for (auto& ch : data) {
            if (ch == ',') {
                nodes.push_back(str);
                str.clear();
            } else {
                str.push_back(ch);
            }
        }
        return deserialize_helper(nodes);
    }
    TreeNode* deserialize_helper(list<string>& nodes)
    {
        if (nodes.empty()) return nullptr;

        string frist = nodes.front();
        nodes.erase(nodes.begin());
        if (frist == "None") return nullptr;
        TreeNode* root = new TreeNode(stoi(frist));
        
        root->left = deserialize_helper(nodes);
        root->right = deserialize_helper(nodes);
        
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));