[leetcode]449. Serialize and Deserialize BST序列化与反序列化BST
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 search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just 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.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
思路
To makes it the most compact possible, since we just need the order the values were inserted, we do not need to account for null nodes in the string with "#" or "null".
Hence, the final string contains only the values and separators, which makes it the most compact possible.
1. 在encode时候,don't account for null nodes
2. 在decode时候,不再用queue来存整个treenode的信息,而是用大小为1的数组idx来track当前扫到哪一个node了, 用idx来拿到该node value值(即mock up a pass-by-address process)。通过BST的attribute (left < root < right)来build tree.
代码
public class Codec { // Encodes a tree to a single string. public String serialize(TreeNode root) { StringBuilder sb = new StringBuilder(); buildString(root, sb); return sb.toString(); } private void buildString(TreeNode root, StringBuilder sb) { if (root == null) return; sb.append(root.val).append(","); buildString(root.left, sb); buildString(root.right, sb); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if(data.length() == 0) return null; // use idx to mockup a pass-by-address int[] idx = new int[]{0}; return buildTree(data.split(","), idx, Integer.MIN_VALUE, Integer.MAX_VALUE); } private TreeNode buildTree(String[] strArr, int[] idx, int min, int max) { if (idx[0] == strArr.length) return null; int val = Integer.parseInt(strArr[idx[0]]); // Go back if out of boundary if (val < min || val > max) return null; TreeNode root = new TreeNode(val); // move to next address idx[0]++; // corresponding to encode pre-order root.left = buildTree(strArr, idx, min, val); root.right = buildTree(strArr, idx, val, max); return root; } }
最新文章
- HDU 3333 &; 主席树
- Spark Idea Maven 开发环境搭建
- BZOJ2062 : 素颜2(face2)
- 挺好看的CSS
- Android Activity生命周期 onSaveInstanceState和onRestoreInstanceState
- 如何将DataTable转换成List<;T>;呢?
- python----------进程、线程、协程
- 系统简单的UIImagePickerController
- 怎样在Android本地视频播放器开发
- ELK日志收集分析系统配置
- 仿百度壁纸客户端(二)——主页自定义ViewPager广告定时轮播图
- java8新特性学习笔记链接
- 【PgSQL安装(含配置)】PostgreSQL简称PgSQL,是1980以加利福尼亚大学开发的DBMS,严格遵守标准SQL。
- Will vs Be Going To vs Present Continuous: Talk About the Future in English
- mfc CImageList和CListCtrl
- log4j1 修改FileAppender解决当天的文件没有日期后缀
- ArrayList(JDK1.9)
- django QueryDict对象
- @SpringBootApplication的使用
- 关于Unity 获得和使用GetComponent<;MeshFilter>;().mesh时的心得