面试题37：序列化二叉树

题目描述

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

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

二叉树的结点定义如下：

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

解题思路

其实挺简单的，因为空节点已经通过使用符号 # 表示了出来，所以不管是先序、中序、后序还是层序，都能够直接恢复。我的问题在于，对 char* 类型的操作不熟悉，一开始写得时候只能通过 string 类型来强行实现这个功能，而且很莽（某+C大佬的评价）。

错误示范

class Solution {
public:
    char* Serialize(TreeNode *root) {
        if (root == nullptr) {
            return nullptr;
        }

        string result;
        result = to_string(root->val) + '!';
        if (root->left != nullptr) {
            result += string(Serialize(root->left));
        } else {
            result += '#';
        }
        if (root->right != nullptr) {
            result += string(Serialize(root->right));
        } else {
            result += '#';
        }
        return (char*)result.c_str();
    }

    TreeNode* Deserialize(char** str) {
        int value;
        if (**str == '\0' || !readString(str, value)) {
            return nullptr;
        }

        TreeNode* node = new TreeNode(value);
        node->left = Deserialize(str);
        node->right = Deserialize(str);
        return node;
    }

    bool readString(char** str, int& value) {
        if (**str == '#') {
            ++*str;
            return false;
        }

        value = **str - '0';
        ++*str;
        while (**str != '!') {
            value = 10*value + **str - '0';
            ++*str;
        }
        ++*str;
        return true;
    }
}；

在调试这段代码的时候，我发现了一个很神奇的问题：就是在第29行执行完新建对象之后，*str 所指向的字符串变成了空字符串，反复确认之后，确实是有这个问题。想了半天，这个对象的构造函数跟这个字符串没啥关系呀，遂请教了+C大佬，过了一会儿：

+C：真的这么神奇啊

不过很快他就发现，问题不在这里，而是在第20行。这里的 c_str() 是不返回拷贝的，所以 str 的生存时间，取决于这个对象本身的生存时间。于是我猜测，是因为新建对象的时候，回收了第8行 result 对象所占用的内存，所以导致第30行 *str 所指向的字符串变成空字符串了。于是在调试时，执行完 Serialize() 函数之后，我便立刻新建了一个对象，果不其然，复现了这个现象。（说白了还是菜啊）

于是在+C大佬的点拨下，写出了下面的代码：

正确示范

class Solution {
public:
    char* Serialize(TreeNode *root) {
        if (root == nullptr) {
            return nullptr;
        }
        return strdup(_Serialize(root).c_str());
    }

    string _Serialize(TreeNode *root) {
        string result;
        result = to_string(root->val) + '!';
        if (root->left != nullptr) {
            result += _Serialize(root->left);
        } else {
            result += '#';
        }
        if (root->right != nullptr) {
            result += _Serialize(root->right);
        } else {
            result += '#';
        }
        return result;
    }

    TreeNode* Deserialize(char* str) {
        if (str == nullptr) {
            return nullptr;
        }
        return Deserialize(&str);
    }

    TreeNode* Deserialize(char** str) {
        int value;
        if (**str == '\0' || !readString(str, value)) {
            return nullptr;
        }
        auto* node = new TreeNode(value);
        node->left = Deserialize(str);
        node->right = Deserialize(str);
        return node;
    }

    bool readString(char** str, int& value) {
        if (**str == '#') {
            ++*str;
            return false;
        }

        value = **str - '0';
        ++*str;
        while (**str != '!') {
            value = 10*value + **str - '0';
            ++*str;
        }
        ++*str;
        return true;
    }
};

反思

从这道题可以看出，我对C语言风格的字符串操作，以及STL的一些细节还是不够熟悉（STL源代码剖析一下）以及，当一个函数的接口给定的时候，不一定非要去凑他的接口，可以通过调用别的函数，来达到更优雅的写法。

相关链接

• 阅读原文
• 序列化二叉树_牛客网