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.
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: []
Example 3:
Input: root = [1] Output: [1]
Example 4:
Input: root = [1,2] Output: [1,2]
Constraints:
- The number of nodes in the tree is in the range
[0, 104]
. -1000 <= Node.val <= 1000
Rust Solution
use rustgym_util::*;
use std::iter::Peekable;
use std::vec::IntoIter;
struct Codec;
enum Tok {
Op(char),
Num(i32),
}
impl Codec {
fn new() -> Self {
Codec {}
}
fn serialize(&self, root: TreeLink) -> String {
let mut res = "".to_string();
Self::serialize_tree(&root, &mut res);
res
}
fn serialize_tree(root: &TreeLink, s: &mut String) {
s.push('(');
if let Some(node) = root {
let node = node.borrow();
*s += &format!("{}", node.val);
Self::serialize_tree(&node.left, s);
Self::serialize_tree(&node.right, s);
}
s.push(')');
}
fn deserialize(&self, data: String) -> TreeLink {
let tokens = Self::parse_tokens(data);
let mut it = tokens.into_iter().peekable();
Self::parse_tree(&mut it)
}
fn parse_tokens(data: String) -> Vec<Tok> {
let mut it = data.chars().peekable();
let mut res = vec![];
while let Some(c) = it.next() {
if c == '(' || c == ')' {
res.push(Tok::Op(c));
} else {
let mut sign = 1;
let mut x = 0;
if c == '-' {
sign = -1;
} else {
x = (c as u8 - b'0') as i32;
}
while let Some('0'..='9') = it.peek() {
x *= 10;
x += (it.next().unwrap() as u8 - b'0') as i32;
}
res.push(Tok::Num(sign * x));
}
}
res
}
fn parse_tree(it: &mut Peekable<IntoIter<Tok>>) -> TreeLink {
let mut res = None;
it.next();
match it.peek() {
Some(&Tok::Num(x)) => {
it.next();
res = tree!(x, Self::parse_tree(it), Self::parse_tree(it))
}
Some(Tok::Op(')')) => {}
_ => panic!(),
}
it.next();
res
}
}
#[test]
fn test() {
let codec = Codec::new();
let root = tree!(1, tree!(2), tree!(3, tree!(4), tree!(5)));
let res = tree!(1, tree!(2), tree!(3, tree!(4), tree!(5)));
assert_eq!(codec.deserialize(codec.serialize(root)), res);
}
Having problems with this solution? Click here to submit an issue on github.