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
- Serialize the tree by conducting a BFS (Breadth-First-Search) traversal.
- Store each value followed by a space in the string. Use "n " to represent null nodes.
- 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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.