Serialization

题目要求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.将二叉搜索树序列化和反序列化，序列化是指将树用字符串的形式表示，反序列化是指将字符串形式的树还原成原来的样子。 ...

题目要求One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as #. 9 / \ 3 2 / \ / \ 4 1 # 6/ \ / \ / # # # # # #For example, the above binary tree can be serialized to the string “9,3,4,#,#,1,#,#,2,#,6,#,#”, where # represents a null node.Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.Each comma separated value in the string must be either an integer or a character ‘#’ representing null pointer.You may assume that the input format is always valid, for example it could never contain two consecutive commas such as “1,,3”.Example 1:Input: “9,3,4,#,#,1,#,#,2,#,6,#,#“Output: trueExample 2:Input: “1,#“Output: falseExample 3:Input: “9,#,#,1"Output: false思路和代码我们知道，任何两个节点都可以和位于左边的非叶节点构成一棵有三个节点的树。如果我们从右往左看先序遍历，就知道后两个节点如果遇到第三个节点，则该节点就应当是这两个节点的父节点。我们可以将每一个#看做一个根节点，每遇到#就将记录的根节点数加一，当遇到数字时，则代表该数字应当能够和两个节点构成新的树，并且该数字成为新的根节点，因此需要将根节点数量减一。如果在遍历的过程中根节点数量小于1，则说明这棵树有问题。而如果遍历结束之后，剩下的根节点数不等于1，也说明这个先序遍历存在问题。 public boolean isValidSerialization(String preorder) { if(preorder==null) return false; if(preorder.length() == 0) return true; String[] nodes = preorder.split(”,”); int nodeCount = 0; for(int i = nodes.length - 1; i >= 0 ; i–) { if(nodes[i].equals(”#”)) { nodeCount++; } else { nodeCount–; } if(nodeCount <= 0) return false; } return nodeCount == 1; } ...