LeetCode 297. Serialize and Deserialize Binary Tree

DFS BFS

Word count: 446Reading time: 2 min

 2022/01/15 

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.

Method 1 Breadth-First Search (BFS)

Serialize

BFS uses queue to realize. queue : First In First Out (FIFO). Following is the step by step algorithm.

Enqueue root node into the queue. Check the front of the queue.
If front == “null”, return “null”.
sr3. If front != “null”, push the node value into a stringstream.
Enqueue the left and right childs into the queue.
Dequeue the current node.
Loop until the queue is empty.

Code

// Encodes a tree to a single string.
string serialize(TreeNode* root) {
    // stringstream -- storing the result string
    stringstream str; 
    // BFS -- Queue;
    queue<TreeNode*> q;
    // 1. first enqueue the root node
    q.push(root);
    while (!q.empty()) {
        // 2. Check the front of the queue, namely the root node.
        TreeNode* node = q.front();
        if (node == NULL) {
            str << "null" << " ";
        } else {
            // 3. if the front is not NULL, enqueue the left and right children.
            str << node->val << " ";
            q.push(node->left);
            q.push(node->right);
        }
        // 4. dequeue current node 
        q.pop();
    }
    return str.str();
}

Deserialize

Except the first one is the value of the root node, the other node values are paired, corresponding to the left and right child nodes.

Convert the input string to a vector list.
Traverse list, connecting the nodes in order of “left child, right child, left child, right child, …”

Code

TreeNode* deserialize(string data) {
    // 1. Convert the input string to a vector list.
    vector<TreeNode*> list;
    string str_val;
    stringstream str(data);
    while (str >> str_val) {
        if (str_val.size() == 0) return NULL;
        if (str_val == "null") {
            list.push_back(NULL);
        } else {
            list.push_back(new TreeNode(stoi(str_val)));
        }
    }
    // 2. Connecting the nodes in order of "left child, right child, ..."
    int node_index = 1;
    for (int i = 0; i < list.size(); i++) {
        if (list[i]) {
            list[i]->left = list[node_index++];
            list[i]->right = list[node_index++];
        }
    }
    return list[0];
}

Method 2 Depth-First Search (DFS)

Next Post

LeetCode 200. Number of Islands
Previous Post

Contrust Binary Tree from Various Traversals