Leetcode 297. Serialize and Deserialize Binary Tree

Explanation

This problem asks us to write two methods: one to convert a binary tree into a string (serialize), and another to convert that string back into the original binary tree structure (deserialize).

The binary tree is serialized by conducting a breadth-first search (BFS) traversal on the tree. First, it starts from the root, then visits the left and right children, and so on. As we traverse the tree, we build a string representation, where "n" represents a null value.

To deserialize the binary tree, we read back the serialized string and build the tree by following the same order as BFS traversal. We put each node we create into a queue, and use them as the parents for the next values from the string.

Algorithm

1. Serialize the tree by conducting a BFS (Breadth-First-Search) traversal.
2. Store each value followed by a space in the string. Use "n " to represent null nodes.
3. Deserialize the tree back by conducting a similar BFS traversal.

Let's walk through an example:

Example

Input:

1
2
3        1
4       / \
5      2   3
6         / \
7        4   5

Serialize:

String representation: "1 2 3 n n 4 5 "

Deserialize:

Reconstruct the original tree from the string.

Python Solution

1
2python
3from collections import deque
4
5class Solution:
6    def serialize(self, root):
7        """Encodes a tree to a single string."""
8        if not root:
9            return ""
10
11        q = deque([root])
12        s = ""
13        while q:
14            node = q.popleft()
15            if node:
16                s += str(node.val) + " "
17                q.append(node.left)
18                q.append(node.right)
19            else:
20                s += "n "
21        
22        return s
23
24    def deserialize(self, data):
25        """Decodes your encoded data to tree."""
26        if not data:
27            return None
28
29        data = data.split()
30        root = TreeNode(int(data[0]))
31        q = deque([root])
32        i = 1
33        while q and i < len(data):
34            node = q.popleft()
35            if data[i] != "n":
36                node.left = TreeNode(int(data[i]))
37                q.append(node.left)
38            i += 1
39            
40            if data[i] != "n":
41                node.right = TreeNode(int(data[i]))
42                q.append(node.right)
43            i += 1
44
45        return root

C++ Solution

1
2c++
3#include<queue>
4#include<string>
5#include<sstream>
6
7using namespace std;
8
9class Codec {
10public:
11    string serialize(TreeNode* root) {
12        if (!root) return "";
13        queue<TreeNode*> q;
14        q.push(root);
15        string result;
16        while (!q.empty()) {
17            TreeNode* node = q.front();
18            q.pop();
19            if (node) {
20                result += to_string(node->val) + " ";
21                q.push(node->left);
22                q.push(node->right);
23            } else {
24                result += "n ";
25            }
26        }
27        return result;
28    }
29
30    TreeNode* deserialize(string data) {
31        if (data.empty()) return nullptr;
32        istringstream in(data);
33        string val;
34        in >> val;
35        TreeNode* root = new TreeNode(stoi(val));
36        queue<TreeNode*> q;
37        q.push(root);
38        while (in >> val) {
39            TreeNode* node = q.front();
40            q.pop();
41            if (val != "n") {
42                TreeNode* left = new TreeNode(stoi(val));
43                node->left = left;
44                q.push(left);
45            }
46            if (in >> val && val != "n") {
47                TreeNode* right = new TreeNode(stoi(val));
48                node->right = right;
49                q.push(right);
50            }
51        }
52        return root;
53    }
54};

Note: This will work for all valid input as there will always be a valid encoding and decoding for a binary tree structure. However, this may not work if the serialized string does not represent a binary tree.## Java Solution

1
2java
3import java.util.*;
4
5public class Codec {
6    public String serialize(TreeNode root) {
7        if (root == null) {
8            return "";
9        }
10        Queue<TreeNode> queue = new LinkedList<>();
11        queue.add(root);
12        StringBuilder res = new StringBuilder();
13        while (!queue.isEmpty()) {
14            TreeNode node = queue.poll();
15            if (node == null) {
16                res.append("n ");
17                continue;
18            }
19            res.append(node.val).append(" ");
20            queue.add(node.left);
21            queue.add(node.right);
22        }
23        return res.toString();
24    }
25
26    public TreeNode deserialize(String data) {
27        if (data.isEmpty()) {
28            return null;
29        }
30
31        String[] nodes = data.split(" ");
32        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
33        Queue<TreeNode> queue = new LinkedList<>();
34        queue.add(root);
35        
36        for(int i = 1; i < nodes.length; i++) {
37            TreeNode parent = queue.poll();
38
39            if (!nodes[i].equals("n")) {
40                TreeNode left = new TreeNode(Integer.parseInt(nodes[i]));
41                parent.left = left;
42                queue.add(left);
43            }
44
45            if (!nodes[++i].equals("n")) {
46                TreeNode right = new TreeNode(Integer.parseInt(nodes[i]));
47                parent.right = right;
48                queue.add(right);
49            }
50        }
51        
52        return root;
53    }
54}

JavaScript Solution

1
2js
3var Tree = function(val) {
4  this.val = val;
5  this.left = this.right = null;
6};
7
8var Codec = function() {};
9
10Codec.prototype.serialize = function(root) {
11    if(!root) return "n";
12
13    let queue = [root];
14    let result = [];
15
16    while(queue.length) {
17        let node = queue.shift();
18
19        if(!node) {
20            result.push('n');
21            continue;
22        }
23
24        result.push(node.val);
25        queue.push(node.left);
26        queue.push(node.right);
27    }
28
29    return result.join(' ');
30};
31
32Codec.prototype.deserialize = function(data) {
33    if(data === "n") return null;
34
35    let nodes = data.split(' ');
36    let root = new Tree(Number(nodes[0]));
37    let queue = [root];
38    let i = 1;
39
40    while(queue.length) {
41        let node = queue.shift();
42
43        if(nodes[i] !== 'n') {
44            node.left = new Tree(Number(nodes[i]));
45            queue.push(node.left);
46        }
47        i++;
48
49        if(nodes[i] !== 'n') {
50            node.right = new Tree(Number(nodes[i]));
51            queue.push(node.right);
52        }
53        i++;
54    }
55
56    return root;
57};

The JavaScript solution is similar to the solutions in other languages. It creates a queue to conduct a breadth-first search and utilize the JavaScript built-in Array object methods shift and push to manage the queue and build the serialized string. It also utilizes the split method to convert the serialized string back into an array for deserialization.