SerializeAndDeserializeBinaryTree [source code]
public class SerializeAndDeserializeBinaryTree {
static
/****************************************************************************/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null)
return "";
StringBuilder sb = new StringBuilder ();
Queue<OptionalNode> queue = new LinkedList<> ();
queue.offer (new OptionalNode (root));
while (!queue.isEmpty ()) {
int size = queue.size ();
boolean last_level = true;
for (int i = 0; i < size; i++) {
OptionalNode cur = queue.poll ();
sb.append ((cur.valid ? cur.node.val : "null") + ",");
if (cur.valid) {
if (cur.node.left != null) {
queue.offer (new OptionalNode (cur.node.left));
last_level = false;
} else {
queue.offer (new OptionalNode (null));
}
if (cur.node.right != null) {
queue.offer (new OptionalNode (cur.node.right));
last_level = false;
} else {
queue.offer (new OptionalNode (null));
}
}
}
if (last_level)
break;
}
return sb.toString ();
}
class OptionalNode {
boolean valid = false;
TreeNode node;
OptionalNode (TreeNode n) {
this.node = n;
if (n != null)
valid = true;
}
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.length () == 0)
return null;
String[] tokens = data.split (",");
TreeNode root = new TreeNode (Integer.parseInt (tokens[0]));
int pos = 1;
Queue<TreeNode> queue = new LinkedList<> ();
queue.offer (root);
while (!queue.isEmpty ()) {
int size = queue.size ();
for (int i = 0; i < size; i++) {
TreeNode cur = queue.poll ();
if (pos >= tokens.length)
break;
Integer left = tokens[pos].equals ("null") ? null : Integer.parseInt (tokens[pos]);
if (left != null) {
cur.left = new TreeNode (left);
queue.offer (cur.left);
}
if (++pos >= tokens.length)
break;
Integer right = tokens[pos].equals ("null") ? null : Integer.parseInt (tokens[pos]);
if (right != null) {
cur.right = new TreeNode (right);
queue.offer (cur.right);
}
pos++;
}
}
return root;
}
}
/****************************************************************************/
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
public static void main(String[] args) {
SerializeAndDeserializeBinaryTree.Codec tester = new SerializeAndDeserializeBinaryTree.Codec();
int[][] inputs = {
{},
{1,2,3,4,5,6,7},
{1,2,3,4,5},
{1,2,3,4,10000_00007,10000_00007,5},
{1,2,3,4,5,10000_00007,7,6,10000_00007,10000_00007,9,10000_00007,8},
{-1,0,1},
};
for (int i = 0; i < inputs.length; i++) {
System.out.println(Printer.separator ());
TreeNode root = TreeNode.bfsBuild (inputs[i]);
String ser = tester.serialize (root);
TreeNode deser_root = tester.deserialize (ser);
String str1 = TreeNode.serialize (root), str2 = TreeNode.serialize (deser_root);
System.out.printf ("%s\n%s\n%s\n",
str1, ser, Printer.wrap (str2, str2.equals (str1) ? 92 : 91)
);
}
}
}
感觉就有点像我当时TreeNode里面自己写的那个玩具函数?
感觉这个难点应该是各种corner case的样子;
你要是直接问我怎么设计, 我估计是又想要用括号结构来设计了, 因为感觉deser的时候, 可能简单一些;
但是有点担心的是, 感觉到时候discuss大部分人都会直接做LeetCode给的这个format, 那么我如果选一个不是很普遍的format, 最后就没有办法跟大家对比答案了;
当然, 一个简单的做法就是, 那个用InOrder和PreOrder/PostOrder组合成功的那种, 肯定是可以的, 一个题目而已;
我这里还是直接用LeetCode的这个BFS结构来做好了; 一来我感觉既然LeetCode选择这个format, 那么估计是有其优秀的地方的;
二来是我想了一下, 直接的括号结构, deser的时候, 好像没有那么简单的;
省点时间, 直接搞;
不过我当时好像实际上只写了deser的部分, ser的部分其实没写诶;
写写看, 我估计应该是不难写的, 不然不至于把这个放在这里作为一个官方例子;
就按照他给的这个tree的例子, 好像ser也有点需要考虑的地方的;
两头的括号就不加了, trivial;
有一个优化, 就是比如这这样的tree:
这个最后第三个level的时候, 我的做法会多加一个最后的Null, 也就是4右边的这个Null; 这个感觉是可以调掉的, 不过有没有必要呢? 如果仅仅是为了应付这一题的话, 其实是没有必要的;
如果真的要做, 两种做法, 一种可以最后做完了之后, 从后往前扫一遍, 把所有的trailing null都删了;
另一种...没想好;
顺带提一下, 感觉这个serialization出来的结构, 跟heap好像有点相似?
当然, 并不是说知道了这个就可以很轻松的写代码, 事实上我感觉就算知道是heap, 最后估计还是要借助于一些recursion的来写, 也未必很简单;
然后被test5给break了; 真的恶心了, 他们故意的, 不让我用负数; 我一开始的思路就是直接用负数来作为一个Null的dummy, 现在不让用, 怎么办?
一个trivial的思路就是自己augment这个node class, 直接记录是否是有效的node, 相当于自己加一个valid bit;
但是想到另外一个方法, 是不是可以直接用heap结构来写? 感觉serialization这个问题特定的话, 这个做法可能会好一些;
这个就是被-1给break掉的serialization代码:
public String serialize(TreeNode root) {
if (root == null)
return "";
StringBuilder sb = new StringBuilder ();
Queue<TreeNode> queue = new LinkedList<> ();
queue.offer (root);
while (!queue.isEmpty ()) {
int size = queue.size ();
boolean last_level = true;
for (int i = 0; i < size; i++) {
TreeNode cur = queue.poll ();
sb.append ((cur.val >= 0 ? cur.val : "null") + ",");
if (cur.val >= 0) {
if (cur.left != null) {
queue.offer (cur.left);
last_level = false;
} else {
queue.offer (new TreeNode (-1));
}
if (cur.right != null) {
queue.offer (cur.right);
last_level = false;
} else {
queue.offer (new TreeNode (-1));
}
}
}
if (last_level)
break;
}
return sb.toString ();
}
如果面试官允许这个办法, 用-1来代表特殊值, 比如说, 规定tree里面所有的node都是非负数, 那么这个方法面试的就可以用, 因为很方便; 但是如果不允许, 比如说, tree里面可能有负数, 那么就要想其他的办法了;
heap的方法虽然有诱惑力, 但是有一个问题, 因为heap方法要求的是一个完全完整的tree, 那么最后serialization出来的空间要求会相当的爆炸, 比如1 + 2 + 4 + 8...之类的, 最后实际上是一个指数级别的爆炸; 这个跟我上面这个正常的serialization方法是有区别的, 比如一个1 null 2 null 3 null 4 null 5这样的5个level的left line, 实际上最后如果用heap做法就不得不每一个level都是指数级别的空间都完整存储, 这个是很不好的;
只能用一个wrap这样的东西来做了, 没有什么其他特别好的办法了;
然后很轻松的AC了, 速度是40(16), 不算骄傲, 因为我这个wrap最后的object overhead应该还是挺吓人的;
设计这个wrap node的时候, 注意一点就是, 要完整的delegate, 而不是一个修改的操作; 这个讲的可能不是很明显; think about the alternative, 另外一种做法, 就是optional这个node, 也有left, right, val这些属性, 然后当他的constructor被丢给一个TreeNode的时候, 你可以把这个TreeNode的所有属性都拷贝给这个optional; 这个是一种做法, 但是会比这里这个做法复杂很多;
我这里的做法更简单, 就是一个完全完整的wrap和delegate; 大概是这个结构:
就有点像一个HMM的模型, 蓝色的是真实的TreeNode的结构, 他们之间有edge; 红色的则是我这里的optional, 他们就类似HMM里面的x, 是没有edge相互之间联系的; 他们唯一的作用就是问问自己连接的蓝色的z: 咱干啥? 这样的;
UNFINISHED
editorial
The idea is simple: print the tree in pre-order traversal and use "X" to denote null node and split node with ",". We can use a StringBuilder for building the string on the fly. For deserializing, we use a Queue to store the pre-order traversal and since we have "X" as null node, we know exactly how to where to end building subtress.
public class Codec {
private static final String spliter = ",";
private static final String NN = "X";
// 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 node, StringBuilder sb) {
if (node == null) {
sb.append(NN).append(spliter);
} else {
sb.append(node.val).append(spliter);
buildString(node.left, sb);
buildString(node.right,sb);
}
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Deque<String> nodes = new LinkedList<>();
nodes.addAll(Arrays.asList(data.split(spliter)));
return buildTree(nodes);
}
private TreeNode buildTree(Deque<String> nodes) {
String val = nodes.remove();
if (val.equals(NN)) return null;
else {
TreeNode node = new TreeNode(Integer.valueOf(val));
node.left = buildTree(nodes);
node.right = buildTree(nodes);
return node;
}
}
}
代码比我简单很多啊, 有点丢人了; 他这个好短;
好像他们都是用DFS做的比较多;
另外, 突然想到, 我的做法, 实际上在serialization的时候, 最坏情况是能够做到2倍的空间浪费的:
看看这个, 应该是不难理解的, 假如最后一个level已经很长, 然后只有第一个parent对应的两个child(甚至只有一个child)是valid的, 那么我的做法最后整个最后一个level后面剩下的Null, 全都会给push到serialization里面去; 这个除了最后加一个post-filtering, 自己手动倒序一个扫描删除trailing nulls, 几乎是没有什么特别方便的办法的;
这里的浪费的空间就是几乎是整个最后一行的空间, 也就是整个红色tree空间占用的一半;
last_level并不能解决这个问题, last_level只能告诉你, 咱们这一个level(最后这个level)搞完, 就可以结束了, queue里面剩下的, 不用管了, 都是没用的Null(在这里, 就是左边两个child node下面的4个Null). 但是最后一行本身后面的这么长的gap, 是没有办法解决的;
对应的, last_level其实节省的也是一个2的倍数的空间(你也可以说时间, 毕竟visit多少node, 就给最后的string加多少entry), 自己想想为什么; 这个2倍指的是BestCase; 如果是worst case, 就跟上面这个例子一样, 节省的很少;
回到正题:
这种recursion的代码, 刚开始有点看不懂, 也是挺正常的;
就用小的tree先帮助理解, 他的没一行代码在干什么, 比如就是一个很小的类似1 2 3这样的tree, 就行了;
我还是这句话, 就算是这种小的例子, 也不要抱着胳膊脑袋里面空想, 尤其是serialization的题目, 你想的出来吗? 我麻烦你老师, 动动手行不行;
他这个思路感觉还是有点借鉴那个两个order来重建tree的问题的; 因为是PreOrder, 上来就知道root, 所以搞起来很方便;
但是又有点不同, 比如他deser的过程, 用的是一个BFS, 而不是一个recursion(那个题目当时用的最简单的方法是recursion, 当然也有用Stack作妖的);
哦不对, 他用的还是recursion; 他写了个queue我还以为他准备和我一样用BFS, 但是实际上他最后这个queue应该就是一个类似accum之类的作用而已;
Deque的remove默认好像是removeFirst? 没记错的话; 另外, 上面有一个.append.append这样的操作, 我不知道原来StringBuilder的append居然是可以chain的;
deser的过程也是一个PreOrder的recursion; 不知道怎么解释, 但是上面这个简单的小tree你自己跑一下, 你就发现这个代码看起来简单, 最后实际上复原的时候, 也是很轻松就完成了;
值得学习的一个做法; 这种拿着一个全局的nodes这个list(虽然是参数, 实际上就是全局的), 然后直接让recursion自己按照顺序来进行list里面的区间划分, 好像当时两个order那个题目的一些解法里面也碰到过类似的做法; 我感觉是有点tricky的;
cdai 895 September 17, 2016 8:08 PMReport
Good idea! Could be more concise though. Thanks for sharing!
public String serialize(TreeNode root) {
return serial(new StringBuilder(), root).toString();
}
// Generate preorder string
private StringBuilder serial(StringBuilder str, TreeNode root) {
if (root == null) return str.append("#");
str.append(root.val).append(",");
serial(str, root.left).append(",");
serial(str, root.right);
return str;
}
public TreeNode deserialize(String data) {
return deserial(new LinkedList<>(Arrays.asList(data.split(","))));
}
// Use queue to simplify position move
private TreeNode deserial(Queue<String> q) {
String val = q.poll();
if ("#".equals(val)) return null;
TreeNode root = new TreeNode(Integer.valueOf(val));
root.left = deserial(q);
root.right = deserial(q);
return root;
}
这个人为了代码精简已经有点丧心病狂了; 你看ser函数, 用的这些inline我就不说了, 他故意把整个helper改成一个returned recursion(原po用的是一个mutation recursion), 但是你看helper本身里面基本没有利用这个返回值的操作, 全都是用的直接对str这个accum的操作;
你可能会想这个是为了干什么呢? 他这么写, 唯一的好处就是ser的主函数里面, 可以直接一行return就结束; 对, 就因为这个...
deser的话用returned recursion实际上是没啥毛病的, tree问题本来就经常是returned recursion很占便宜, 这个也是总结过很多次了;
deser函数的主题几乎是没有太多改变的;
比较trivial的改写好吧, 但是upvote很多;
哦不对, 他ser函数的返回值是有用的, 你看他serhelper的本体里面, 有serial(str, root.left).append(",");这种用法之所以成立就是因为返回上来的这个实际上跟参数里传来传去的str是一个指针, 所以直接可以append;
感觉还是挺无聊的;
底下一个人给的自己画的trace:
看看还行;
下面另外一个改写:
public class Codec {
private static final String DELIMITER = "/";
private static final String NULL_NODE = "NULL";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return NULL_NODE + DELIMITER;
return Integer.toString(root.val) + DELIMITER + serialize(root.left) + serialize(root.right);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
LinkedList<String> nodes = new LinkedList<String>();
nodes.addAll(Arrays.asList(data.split(DELIMITER)));
return buildTree(nodes);
}
private TreeNode buildTree(LinkedList<String> nodes) {
String node = nodes.remove();
if (node.equals(NULL_NODE)) return null;
TreeNode root = new TreeNode(Integer.parseInt(node));
root.left = buildTree(nodes);
root.right = buildTree(nodes);
return root;
}
}
看起来还不错是吧?
你再仔细看看呢? 这个人为了ser的代码的简洁, 整个都是完全的用string操作, 而不是用楼主那样的全局mutation的方法来collect. 不能理解这些人的想法, 这样的设计最后复杂度是会非常爆炸的; 事实上, 就算是一个balanced的tree, 最后复杂度都会变成NlgN而不是原来的N, 因为每一个level实际上都会因为string操作承载整个O(N)的复杂度;
如果不是balanced的, 分析好像稍微复杂一些;
差不多了, 这个帖子就这些东西了; 总体来说不是一个特别苦手的hard题. 其他的discuss帖子后面有时间再看;
Problem Description
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.
Example:
You may serialize the following tree:
1
/ \
2 3
/ \
4 5
as "[1,2,3,null,null,4,5]"
Clarification: Just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
Difficulty:Hard
Total Accepted:105.3K
Total Submissions:297.9K
Contributor:Louis1992
Companies
googlefacebookmicrosoftamazonbloomberguberlinkedinyahoo
Related Topics
treedesign
Similar Questions
Encode and Decode StringsSerialize and Deserialize BSTFind Duplicate Subtrees