297 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.

For example, you may serialize the following tree

    1
   / \
  2   3
     / \
    4   5

as

"[1,2,3,null,null,4,5]"

You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself

The Idea:

• The use of ostringstream and istringstream allows us to cleanly delimit serialized words.

• Serialization is pretty simply. We just continue to append to referenced string.

• Deserialization feeds in a referenced istream object which ensures that it will be read in linearly. The key in understand how it works is that we first build a stack of TreeNode's in a pre-order fashion before connecting the tree together.

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        ostringstream os;
        serialize(root, os);
        return os.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream is(data);
        return deserialize(is);
    }

private:

    void serialize(TreeNode* root, ostringstream &os) {
        if (root) {
            os << root->val << " ";
            serialize(root->left, os);
            serialize(root->right, os);
        }
        else os << "null ";
    }


    TreeNode* deserialize(istringstream &is) {
        string cur_str;
        is >> cur_str;
        if (cur_str == "null") return nullptr;

        TreeNode *temp = new TreeNode(stoi(cur_str));
        temp->left = deserialize(is);
        temp->right = deserialize(is);

        return temp;
    }
};

Python

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """

        pre_order = []
        def dfs(root):
            if (root):
                pre_order.append(str(root.val))
                dfs(root.left)
                dfs(root.right)
            else:
                pre_order.append('#')

        dfs(root)
        return ','.join(pre_order)

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """

        data = data.split(',')
        global_iter = [0]
        def dfs(i):
            if data[i[0]] == '#':
                return None
            else:
                next_root = TreeNode(int(data[i[0]]))
                i[0] += 1
                next_root.left = dfs(i)
                i[0] += 1
                next_root.right = dfs(i)
                return next_root
        return dfs(global_iter)



# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))