【HARD】Serialize and Deserialize Binary Tree

发布于: 2019-01-01 19:40
阅读: 77
评论: 0
喜欢: 0

问题

原题链接:https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

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.

分析过程

  • 输入:一棵二叉树 或 一段序列化数据结构
  • 输出:一段序列化数据结构 或 一棵二叉树
  • 思路:
    • 归档可以使用树的深度遍历和广度遍历,我使用了深度遍历。
    • 归档的关键是要把空节点也输出,否则解档递归不知道何时应该返回。
    • 解档的返回条件是找到了空节点,非法节点可以截断或者直接 fatal。

解决方法

class Codec {
public:
    
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (!root) {
            return "null";
        }
        vector<string> vec;
        _serialize(root, vec);
        string result = vec[0];
        for (int i = 1; i < vec.size(); i++) {
            result += "," + vec[i];
        }
        return result;
    }
    
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data == "" || data == "nullptr") {
            return nullptr;
        }
        vector<string> vec;
        istringstream stream(data);
        string tmp;
        while (getline(stream, tmp, ',')) {
            vec.push_back(tmp);
        }
        int i = 0;
        return _deserialize(vec, &i);
    }
private:
    
    void _serialize(TreeNode *root, vector<string>& vec) {
        char buf[5];
        // 把节点的值输出
        sprintf(buf, "%d", root->val);
        vec.push_back(string(buf));
        // 递归输出左右子树,如果是空的则输出 null
        root->left ? _serialize(root->left, vec) : vec.push_back("null");
        root->right ? _serialize(root->right, vec) : vec.push_back("null");;
    }
    
    TreeNode *_deserialize(vector<string>& vec, int *index) {
        TreeNode *node = _deserializeNode(vec.at(*index));
        ++*index;
        if (!node) {
            return nullptr;
        }
        // 递归解档左右子树
        node->left = _deserialize(vec, index);
        node->right = _deserialize(vec, index);
        return node;
    }
    
    static TreeNode *_deserializeNode(string& str) {
        if (str == "null") {
            return nullptr;
        } else {
            int v;
            if (sscanf(str.c_str(), "%d", &v) != 1) {
                // 不是 null,也不是合法的数字
                // 可以 fatal,也可以忽略直接截断
                return nullptr;
            }
            return new TreeNode(v);
        }
    }
};

Thanks for reading.

All the best wishes for you! 💕