[LeetCode] 297. Serialize and Deserialize Binary Tree

297. Serialize and Deserialize Binary Tree

week6

难度：Hard

题目链接

---

题目描述

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Example:

You may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]"

Clarification: The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

---

题目分析

  题目的意思是将一棵树序列化为字符串，而且序列化后的树能够经过反序列化变为原来的树结构。序列化的意思是将状态信息转化为可以存储和传输的形式，这在很多场合都能够用到，可以使自定义对象持久化，方便传输对象，以及便于程序维护等等。

---

解题思路

  题目已经给出了LeetCode所用的二叉树的序列化的形式，即将二叉树的每个节点的值存在一个字符串中，用标点符号隔开。观察其顺序可以发现是使用分层方式来构造的，因此我们可以用分层遍历的方式来构造这个字符串，然后再还原。

  使用分层遍历，构造一个队列存储遍历的节点并将子节点放在队列中，从而逐层遍历，构造字符串，注意也要把空节点放进去，否则将无法还原为原来的树。

  得到字符串并以“，”为分割点分割成不同的字符串节点，然后使用队列构造回原来的树。

---

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include <string>
#include <queue>
using namespace std;
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string sertree;
        queue<TreeNode*> queue;
        queue.push(root);
        while(!queue.empty()){
            TreeNode* node = queue.front();
            queue.pop();
            if(sertree.length()>0) {
                sertree += ",";
            }
            if(node == nullptr) {
                sertree += "null";
            }
            else {
                sertree += std::to_string(node->val);
                queue.push(node->left);
                queue.push(node->right);
            }
        }
        return sertree;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data == "null") {
            return nullptr;
        }
        vector<string> treeNodes = split(data,",");
        TreeNode* root = new TreeNode(atoi(treeNodes[0].c_str()));
        queue<TreeNode*> queue; 
        queue.push(root);
        for(int i = 1; i < treeNodes.size(); i+=2){
            TreeNode* node = queue.front();
            queue.pop();
            if(treeNodes[i] != "null"){
                TreeNode* left = new TreeNode(atoi(treeNodes[i].c_str()));
                node->left = left;
                queue.push(left);
            }
            if(treeNodes[i+1] != "null"){
                TreeNode* right = new TreeNode(atoi(treeNodes[i+1].c_str()));
                node->right = right;
                queue.push(right);
            }
        }
        return root;
    }
    vector<string> split(const string& str, const string& delim) {
        vector<string> res;
        if("" == str) return res;
        //先将要切割的字符串从string类型转换为char*类型
        char * strs = new char[str.length() + 1] ;
        strcpy(strs, str.c_str()); 

        char * d = new char[delim.length() + 1];
        strcpy(d, delim.c_str());

        char *p = strtok(strs, d);
        while(p) {
            string s = p; //分割得到的字符串转换为string类型
            res.push_back(s); //存入结果数组
            p = strtok(NULL, d);
        }

        return res;
    }
};


// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

---

Note

1. 注意c中的string中没有split这个函数，所以要自己写一个split函数，使用c里的strtok方法，先将字符串转化成Char数组类型，（注意char*最后有一个终止符，length+1），然后调用这个方法来处理char数组，通过循环进行逐步分割，再变成string，最后传出结果vector;

2. 反序列化为树结构时，需要注意要去除空节点。否则将会出现访问空节点的错误，另外因为存放了null，所以每一次可以同时访问左右两个节点。

3. 除了使用分层序列化之外，还有许多方法，比如使用深度+递归，广度遍历也可以，只要能够做到反序列化从转化为原来的树结构即可。

总结

  在这个题目中，我发现JAVA和C其实很大区别的，写多了JAVA之后，发现许多方法都在c没有提供，比如split，还有许多很方便使用的Likedlist等等数据结构。所以在JAVA中许多包装的方法还是挺好用的，以前还觉得很相似，但是现在发现在应用上的便利性上差距挺大的，所以遇到问题可以先使用JAVA来完成一下，确定解决的方法，然后再使用C++来实现。

  看了一下除此之外有人使用map<long,TreeNode*>来进行存储，直接偷鸡使用全局变量存储状态。。。不算是序列化。而且题目已经标明了不可用存储状态的做法了。