leetcode/
ser_des_bst.rs

1//! # 449. 序列化和反序列化二叉搜索树
2//!
3//! 难度 中等
4//!
5//! 序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。
6//!
7//! 设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。
8//!
9//! 编码的字符串应尽可能紧凑。
10//!
11//!  
12//!
13//! ## 示例 1：
14//!
15//! ```text
16//! 输入：root = [2,1,3]
17//! 输出：[2,1,3]
18//! ```
19//!
20//! ## 示例 2：
21//!
22//! ```text
23//! 输入：root = []
24//! 输出：[]
25//! ```
26//!  
27//! ## 提示：
28//!
29//! - 树中节点数范围是 `[0, 104]`
30//! - `0 <= Node.val <= 104`
31//! - 题目数据 保证 输入的树是一棵二叉搜索树。
32//!  
33//!
34//! 注意：不要使用类成员/全局/静态变量来存储状态。 你的序列化和反序列化算法应该是无状态的。
35//!
36//! See [leetcode](https://leetcode-cn.com/problems/serialize-and-deserialize-bst/)
37
38use crate::TreeNode;
39
40use std::rc::Rc;
41use std::cell::RefCell;
42
43pub struct Codec {}
44
45/**
46 * `&self` means the method takes an immutable reference.
47 * If you need a mutable reference, change it to `&mut self` instead.
48 */
49impl Codec {
50    fn new() -> Self {
51        Self {}
52    }
53
54    fn ser(&self, root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Option<i32>> {
55        root.map_or(vec![None], |node| {
56            let mut node = node.as_ref().borrow_mut();
57            let left = node.left.take();
58            let right = node.right.take();
59            let mut l = self.ser(left);
60            let mut r = self.ser(right);
61            let mut res = vec![];
62            res.append(&mut l);
63            res.append(&mut r);
64            res.append(&mut vec![Some(node.val)]);
65            res
66        })
67    }
68
69    pub fn serialize(&self, root: Option<Rc<RefCell<TreeNode>>>) -> String {
70        self.ser(root).iter().map(|v| {
71            v.map_or("".to_string(), |v| format!("{}", v)) }).collect::<Vec<_>>().as_slice().join(" ")
72    }
73
74    fn des(&self, data: &mut Vec<Option<i32>>) -> Option<Rc<RefCell<TreeNode>>> {
75        if data.is_empty() {
76            return None;
77        }
78
79        data.pop().and_then(|val| val).map(|val| {
80            let right = self.des(data);
81            let left = self.des(data);
82            let node = TreeNode {
83                val,
84                left: left,
85                right: right,
86            };
87            Rc::new(RefCell::new(node))
88        })
89    }
90
91    pub fn deserialize(&self, data: String) -> Option<Rc<RefCell<TreeNode>>> {
92        if data.is_empty() {
93            return None;
94        }
95        let mut d: Vec<Option<i32>> = data.split(' ').map(|s| {
96            s.parse().ok()
97        }).collect();
98        self.des(&mut d)
99    }
100}
101
102/*
103 * Your Codec object will be instantiated and called as such:
104 * let obj = Codec::new();
105 * let data: String = obj.serialize(strs);
106 * let ans: Option<Rc<RefCell<TreeNode>>> = obj.deserialize(data);
107 */
108
109#[cfg(test)]
110mod tests {
111    use crate::tree;
112    use super::*;
113
114    #[test]
115    fn test() {
116        let codec = Codec::new();
117        let t = |n| codec.deserialize(codec.serialize(n));
118        assert_eq!(tree![2,1,3], t(tree![2,1,3]));
119        assert_eq!(tree![], t(tree![]));
120        assert_eq!(tree![4,2,7,1,3,6,9], t(tree![4,2,7,1,3,6,9]));
121        assert_eq!(tree![4,2,7,null,null,6,9], t(tree![4,2,7,null,null,6,9]));
122    }
123}
leetcode/ser_des_bst.rs

leetcode/
ser_des_bst.rs
