描述

这是一篇针对初学者的题解，共用两种方法解决。
知识点：二叉树，先序遍历，层次遍历
难度：二星

题解

题目描述：给定一颗二叉树，将其序列化和反序列化。

方法一：先序遍历实现

预备知识：先序遍历的递归实现：

void pre_order(TreeNode *root) {
    if (!root) {
        return;
    }

    // process root
    // ...
    pre_order(root->left);
    pre_order(root->right);
}

对于本题来说，可以套用上述模板。
假设序列化的结果为字符串 str, 初始str = "".根据要求，遇到nullptr节点，str += "#"
遇到非空节点，str += "val" + "!"; 假设val为3， 就是 str += "3!"

所以，最终的代码为：

char* Serialize(TreeNode *root) {    
    if (!root) {
        return "#";
    }

    string res = to_string(root->val);
    res.push_back(',');

    char* left = Serialize(root->left);
    char* right = Serialize(root->right);

    char* ret = new char[strlen(left)+strlen(right)+res.size()];
    // 如果是string类型，直接用operator += ,这里char* 需要用函数
    strcpy(ret,res.c_str());
    strcat(ret,left);
    strcat(ret,right);

    return ret;
}

反序列化的结果，就是根据先序遍历，再重建二叉树即可。
代码如下：

// 参数使用引用&， 以实现全局变量的目的
TreeNode* deseri(char *&s) {
    if (*s == '#') {
        ++s;
        return nullptr;
    }

    // 构造根节点值
    int num = 0;
    while (*s != ',') {
        num = num * 10 + (*s - '0');
        ++s;
    }
    ++s; 
    // 递归构造树
    TreeNode *root = new TreeNode(num);
    root->left = deseri(s);
    root->right = deseri(s);

    return root;
}

TreeNode* Deserialize(char *str) {
    return deseri(str);
}

中序遍历，后序遍历大致都差不多。

方法二：层次遍历实现

层次遍历采用队列实现。跟先序遍历的思想差不多，无非都是把树的所有数据遍历一遍，然后记录下来。
层次遍历模板：

void bfs(TreeNode *root){
    queue<TreeNode*> qt;
    qt.push(root);
     string s;
    while (!qt.empty())
    {
        // pop operator
        TreeNode *node = qt.front();
        qt.pop();

        // process node
        if (node == NULL)
        {
            s.push_back('#');
            s.push_back(',');
            continue;
        }
        s += to_string(node->val);
        s.push_back(',');

        // push operator
        qt.push(node->left);
        qt.push(node->right);

    }
}

序列化的操作直接根据模板套即可。代码如下：

char* Serialize(TreeNode *root)
{
    string s;
    queue<TreeNode*> qt;
    qt.push(root);

    while (!qt.empty())
    {
        // pop operator
        TreeNode *node = qt.front();
        qt.pop();
        // process null node
        if (node == nullptr)
        {
            s.push_back('N');
            s.push_back(',');
            continue;
        }
        // process not null node
        s += to_string(node->val);
        s.push_back(',');
        // push operator
        qt.push(node->left);
        qt.push(node->right);

    }

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

    return ret;
}

反序列化就是根据层次遍历在走一遍即可。
代码如下：

TreeNode* Deserialize(char *str)
{
    if (str == nullptr) {
        return nullptr;
    }
    // 可用string成员函数
    string s(str);
    if (str[0] == '#') {
        return nullptr;
    }

    // 构造头结点
    queue<TreeNode*> nodes;
    TreeNode *ret = new TreeNode(atoi(s.c_str()));
    s = s.substr(s.find_first_of(',') + 1);
    nodes.push(ret);
    // 根据序列化字符串再层次遍历一遍，来构造树
    while (!nodes.empty() && !s.empty())
    {
        TreeNode *node = nodes.front();
        nodes.pop();
        if (s[0] == '#')
        {
            node->left = nullptr;
            s = s.substr(2);
        }
        else
        {
            node->left = new TreeNode(atoi(s.c_str()));
            nodes.push(node->left);
            s = s.substr(s.find_first_of(',') + 1);
        }

        if (s[0] == '#')
        {
            node->right = nullptr;
            s = s.substr(2);
        }
        else
        {
            node->right = new TreeNode(atoi(s.c_str()));
            nodes.push(node->right);
            s = s.substr(s.find_first_of(',') + 1);
        }
    }
    return ret;
}

此题主要考察对树的遍历和构造树。