297. Serialize and Deserialize Binary Tree

Problem Statement

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.

Clarification: The input/output 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.

Example 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 104].
-1000 <= Node.val <= 1000

Intuition

Approach:

We did by preorder
Root->left->right

Traversed like that

Links

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/

Video Links

Approach 1:

C++

class Codec {
public:
        // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string result = "";
        preorderSerialize(root, result);
        cout<<result<<endl;
        return result;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int index = 0;
        return preorderDeserialize(data, index);
    }
    
    // serialize the tree through preorder traversal
    // seperate the node value by ',', a NULL node is represented as '*'
    void preorderSerialize(TreeNode* node, string& result) {
        if (node == NULL) {
            result += "*,";
            return;
        }
        result += to_string(node->val) + ',';
        preorderSerialize(node->left, result);
        preorderSerialize(node->right, result);
    }
    
    // also deserialize the tree through preorder traversal
    TreeNode* preorderDeserialize(string& data, int& index) {
        if (data[index] == '*') {
            index += 2;
            return NULL;
        }
        // check if the value of the node is negative
        bool negative = false;
        if (data[index] == '-') {
            negative = true;
            index++;
        }
        int value = 0;
        while (data[index] != ',') {
            value = value * 10 + (data[index] - '0');
            index++;
        }
        if (negative) {
            value = -value;
        }
        TreeNode* node = new TreeNode(value);
        index++;
        node->left = preorderDeserialize(data, index);
        node->right = preorderDeserialize(data, index);
        return node;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++