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);
}