【HARD】Serialize and Deserialize Binary Tree

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

问题

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 TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    
    TreeNode(int val) {
        this->val = val;
        this->left = nullptr;
        this->right = nullptr;
    }
    
public:
    // 从向量解档
    static TreeNode *UnarchiveFromVector(vector<string>& vec) {
        int index = 0;
        return _unarchiveFromVector(vec, &index);
    }
    
    // 归档到一个向量
    vector<string> ArchiveToVector() {
        vector<string> vec;
        _archiveToVector(vec);
        return vec;
    }
    
private:
    // 递归所有节点归档到一个向量里
    void _archiveToVector(vector<string>& vec) {
        char buf[20];
        // 把节点的值输出
        sprintf(buf, "%d", val);
        vec.push_back(string(buf));
        // 递归输出左右子树,如果是空的则输出 null
        left ? left->_archiveToVector(vec) : vec.push_back("null");
        right ? right->_archiveToVector(vec) : vec.push_back("null");
    }
    
    // 递归从向量解档
    static TreeNode *_unarchiveFromVector(vector<string>& vec, int *index) {
        // 尝试从字符串初始化节点,如果是空节点就跳出递归
        TreeNode *node = _unarchiveFromString(vec.at(*index));
        ++*index;
        if (!node) {
            return nullptr;
        }
        // 递归解档左右子树
        node->left = _unarchiveFromVector(vec, index);
        node->right = _unarchiveFromVector(vec, index);
        return node;
    }
    
    // 从字符串初始化一个节点
    static TreeNode *_unarchiveFromString(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);
        }
    }
};

int main() {
    
    TreeNode *tree = ({
        TreeNode *n1 = new TreeNode(1);
        TreeNode *n2 = new TreeNode(2);
        TreeNode *n3 = new TreeNode(3);
        TreeNode *n4 = new TreeNode(4);
        TreeNode *n5 = new TreeNode(5);
        
        n1->left = n2;
        n1->right = n3;
        n3->left = n4;
        n3->right = n5;
        
        n1;
    });
    
    vector<string> vec = tree->ArchiveToVector();
    TreeNode *newTree = TreeNode::UnarchiveFromVector(vec);
    
    return 0;
}

Thanks for reading.

All the best wishes for you! 💕