【LeetCode】【剑指offer】【序列化二叉树】

剑指 Offer 37. 序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树。

你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例：

输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

 

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 

 反序列化，就是我们要把我们得到的字符串转换为一颗二叉树。这里官方传给我们的数据是一整个string，并且其中每一个数据是用逗号（英文）分割的，然后null使用None表示的。所以我们先需要遍历整一个string，每次遇到一个逗号就将逗号之间的字符串压入我们的结果队列中。最后，我们在构建二叉树的时候，采用前序遍历的方法。每构建完成一个结点，就将我们的队列的队头的数据弹出。并最终返回根结点。

序列化，就是将我们的二叉树转换成一个字符串。这里我们同样也是采用前序遍历的方法，同时用一个字符串来记录当前遍历到的数据。如果是null就在我们的字符串后面加上（None,），如果是具体的数据，就将我们的数据转换成字符串后再加到我们的结果字符串中。 

这里需要注意对于反序列化中的队列和 序列化中的返回字符串结果都需要加上&，否则临时拷贝是没有办法对源数据产生影响的。

class Codec {
public:

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

    string serialize(TreeNode* root) {
        string ret;
        rserialize(root, ret);
        return ret;
    }



    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        queue<string> dataArray;
        string tmp;
        for(auto& ele:data)
        {
            if(ele==',')
            {
                dataArray.push(tmp);
                tmp.clear();
            }
            else
            {
                tmp.push_back(ele);
            }
        }
        if(tmp.empty()!=true)
        {
            dataArray.push(tmp);
            tmp.clear();
        }

        TreeNode* result=BinaryTreeCreate(dataArray);
        return result;
    }

    //注意这里一定要加上引用，不然是没办法对原数据进行修改的。
    TreeNode* BinaryTreeCreate(queue<string>& dataArray)
    {
        if(dataArray.front()=="None")
        {
            dataArray.pop();
            return nullptr;
        }
        TreeNode *dst=new TreeNode(stoi(dataArray.front()));
        dataArray.pop();

        dst->left=BinaryTreeCreate(dataArray);
        dst->right=BinaryTreeCreate(dataArray);
        return dst;
    }
};