RUST GYM Leetcode 449 Serialize and Deserialize BST Rust Solution

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, 10⁴].
0 <= Node.val <= 10⁴
The input tree is guaranteed to be a binary search tree.

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 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(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!(2, tree!(1), tree!(3));
    let ans = tree!(2, tree!(1), tree!(3));
    assert_eq!(codec.deserialize(codec.serialize(root)), ans);
}

Having problems with this solution? Click here to submit an issue on github.