Algorithm
Problem Name: 449. Serialize and Deserialize BST
Serialization is 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 search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.
The encoded string should be as compact as possible.
Example 1:
Input: root = [2,1,3] Output: [2,1,3]
Example 2:
Input: root = [] Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 104]. 0 <= Node.val <= 104- The input tree is guaranteed to be a binary search tree.
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
public class Codec {
public String serialize(TreeNode root) {
if (root == null) {
return "#";
}
StringBuilder sb = new StringBuilder();
dfsSerialize(root, sb);
return sb.toString().trim();
}
private void dfsSerialize(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append("#").append(" ");
return;
}
sb.append(root.val).append(" ");
dfsSerialize(root.left, sb);
dfsSerialize(root.right, sb);
}
public TreeNode deserialize(String data) {
Queue < String> queue = new LinkedList<>(Arrays.asList(data.split("\\s+")));
return dfsDeserialize(queue);
}
private TreeNode dfsDeserialize(Queue < String> queue) {
if (queue.isEmpty()) {
return null;
}
String removed = queue.remove();
if (removed.equals("#")) {
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(removed));
root.left = dfsDeserialize(queue);
root.right = dfsDeserialize(queue);
return root;
}
}
Input
Output
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const serialize = function(root) {
const sb = [];
buildString(root, sb);
sb.pop();
return sb.join("");
};
function buildString(node, sb) {
if (node == null) return;
sb.push(node.val);
sb.push(splitter);
buildString(node.left, sb);
buildString(node.right, sb);
}
const deserialize = function(data) {
if (data.length === 0) return null;
const pos = [0];
return buildTree(
data.split(splitter),
pos,
Number.MIN_SAFE_INTEGER,
Number.MAX_SAFE_INTEGER
);
};
function buildTree(nodes, pos, min, max) {
if (pos[0] === nodes.length) return null;
let val = +nodes[pos[0]];
if (val < min || val > max) return null;
const cur = new TreeNode(val);
pos[0] += 1;
cur.left = buildTree(nodes, pos, min, val);
cur.right = buildTree(nodes, pos, val, max);
return cur;
}
Input
Output
#3 Code Example with C# Programming
Code -
C# Programming
sing System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LeetCode
{
public class _0449_SerializeAndDeserializeBST
{
public string serialize(TreeNode root)
{
var sb = PostOrder(root, new StringBuilder());
if (sb.Length > 0)
sb.Remove(sb.Length - 1, 1);
return sb.ToString();
}
public TreeNode deserialize(string data)
{
if (string.IsNullOrEmpty(data)) return null;
var nums = data.Split().Select(n => int.Parse(n)).ToList();
return Helper(int.MinValue, int.MaxValue, nums);
}
private StringBuilder PostOrder(TreeNode root, StringBuilder sb)
{
if (root == null) return sb;
PostOrder(root.left, sb);
PostOrder(root.right, sb);
sb.Append(root.val);
sb.Append(" ");
return sb;
}
private TreeNode Helper(int lower, int upper, IList < int> nums)
{
if (nums.Count == 0) return null;
var value = nums.Last();
if (value < lower || value > upper) return null;
nums.RemoveAt(nums.Count - 1);
var root = new TreeNode(value);
root.right = Helper(value, upper, nums);
root.left = Helper(lower, value, nums);
return root;
}
}
}
Input
Output