二叉树的序列化和反序列化

明确概念

首先明确一下什么是 序列化，和反序列化。

1. 序列化(serialization)：是将对象的状态信息转换为可以存储或传输形式的过程；
   在序列化期间，对象将其状态写入临时或者永久性存储区域;比如说通过前序遍历得到的序列，存储在数组中，这就是序列化的过程。
2. 反序列化(Unserialization): 是序列化的逆过程，也就是将字节序恢复为对象的过程，如通过二叉树的前中序，构造二叉树的过程就是反序列化。

参考代码

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};

//在序列化和反序列化中，可以同时使用一种遍历方法，比如都使用前序遍历，得到 outstream ===instream,然后通过instream，读取后采用前序遍历即可反序列化成功。
class Solution {
public:
    //存在一颗树，将树序列化，并将序列化后的信息流输入到流stream中
    //使用前序遍历的方式，将节点val序列化成字节序输入到outstream中
    void Serialize(TreeNode *root, ostream& outstream) {
        if (root == NULL) {
            outstream <<"#,";
            return;
        }
        outstream <<root->value<<',';
        Serialize(root->left, outstream);
        Serialize(root->right,outstream);
    }

    //不存在一棵树，但含有输入流stream，将流中的数据反序列化生成树，*root指向树的根节点
    //由于我们清楚输入流stream中的字节序是前序遍历的结果，那反序列化时也必须使用前序方式，才能正确构造一颗树
    void Deserialize(TreeNode **root, istream& instream) {
        int num;
        if (ReadStream(instream, &num)) {
            //构造根节点
            *root = new TreeNode(num);
            (*root)->left = NULL;
            (*root)->right = NULL;
            //构造左右子节点
            Deserialize(&((*root)->left),instream);
            Deserialize(&((*root)->right),instream);
        }
    }

private:
    //每次从stream中读取一个数字或者“#”，是数字返回true，否则返回false
    bool ReadStream(istream& instream, int* num){
        if (instream.eof()) {
            return false;
        }
        //初始化缓冲区
        char buf[10];
        buf[0]='\0';

        char temp;
        instream>>temp;

        //从流中读取分隔符前面的第一字符串；
        int i=0;
        while (!instream.eof() && temp !=",") {
            buf[i++] = temp;
            instream >> temp;
        }

        bool isNumeric = false;
        //一个trick，当buf的第一位不是#的时候，后面的才有可能是数字
        if (i>0 && buf[0]!='#') {
            *num = atoi(buf);
            isNumeric = true;
        }

        return isNumeric;
    }
};

References

• 牛客剑指offer专题
• zhedahht