LeetCode 297 - Serialize and Deserialize Binary Tree
Serialization/Deserialization of a Binary Tree | LeetCode
Design an algorithm and write code to serialize and deserialize a binary tree. Writing the tree to a file is called ‘serialization’ and reading back from the file to reconstruct the exact same binary tree is ‘deserialization’.
We may also use level-order traversal to write/read binary tree. Level-order traversal works because like pre-order traversal, we see the parent node before its child nodes.
Further Thoughts:
There is an obvious shortcoming in this method, that is: a sentinel is required to represent empty nodes. What if we need to store strings that can contain any characters (including the sentinel) in the binary tree? Could you come up with a solution to overcome this shortcoming?
One simple optimization is to store a separate bit with every node to indicate that the node is internal or external. This way we don’t have to store two markers with every leaf node as leaves can be identified by extra bit. We still need marker for internal nodes with one child. For example in the following diagram ‘ is used to indicate an internal node set bit, and ‘/’ is used as NULL marker. The diagram is taken from here.
Please note that there are always more leaf nodes than internal nodes in a Binary Tree (Number of leaf nodes is number of internal nodes plus 1, so this optimization makes sense.
http://hehejun.blogspot.com/2015/01/lintcodeserialization-and.html
Read full article from Serialization/Deserialization of a Binary Tree | LeetCode
Serialization/Deserialization of a Binary Tree | LeetCode
Design an algorithm and write code to serialize and deserialize a binary tree. Writing the tree to a file is called ‘serialization’ and reading back from the file to reconstruct the exact same binary tree is ‘deserialization’.
In order for the nodes to be inserted at the correct place, we would need to output the NULL nodes using some kind of sentinel (Here, we use ‘#‘ as the sentinel) as we are doing pre-order traversal.
Assume we have a binary tree below:
_30_ / \ 10 20 / / \ 50 45 35
Using pre-order traversal, the algorithm should write the following to a file:
30 10 50 # # # 20 45 # # 35 # #
void writeBinaryTree(BinaryTree *p, ostream &out) {
if (!p) {
out << "# ";
} else {
out << p->data << " ";
writeBinaryTree(p->left, out);
writeBinaryTree(p->right, out);
}
}
Deserializing a Binary Tree:
Reading the binary tree from the file is similar. We read tokens one at a time using pre-order traversal. If the token is a sentinel, we ignore it. If the token is a number, we insert it to the current node, and traverse to its left child, then its right child.
void readBinaryTree(BinaryTree *&p, ifstream &fin) {
int token;
bool isNumber;
if (!readNextToken(token, fin, isNumber))
return;
if (isNumber) {
p = new BinaryTree(token);
readBinaryTree(p->left, fin);
readBinaryTree(p->right, fin);
}
}
Alternative Solution:We may also use level-order traversal to write/read binary tree. Level-order traversal works because like pre-order traversal, we see the parent node before its child nodes.
Further Thoughts:
There is an obvious shortcoming in this method, that is: a sentinel is required to represent empty nodes. What if we need to store strings that can contain any characters (including the sentinel) in the binary tree? Could you come up with a solution to overcome this shortcoming?
function EncodeSuccinct(node n, bitstring structure, array data) {
if n = nil then
append 0 to structure;
else
append 1 to structure;
append n.data to data;
EncodeSuccinct(n.left, structure, data);
EncodeSuccinct(n.right, structure, data);
}
function DecodeSuccinct(bitstring structure, array data) {
remove first bit of structure and put it in b
if b = 1 then
create a new node n
remove first element of data and put it in n.data
n.left = DecodeSuccinct(structure, data)
n.right = DecodeSuccinct(structure, data)
return n
else
return nil
}
http://www.geeksforgeeks.org/serialize-deserialize-binary-tree/
If given Tree is Binary Search Tree?
If the given Binary Tree is Binary Search Tree, we can store it by either storing preorder or postorder traversal. In case of Binary Search Trees, only preorder or postorder traversal is sufficient to store structure information.
If the given Binary Tree is Binary Search Tree, we can store it by either storing preorder or postorder traversal. In case of Binary Search Trees, only preorder or postorder traversal is sufficient to store structure information.
If given Binary Tree is Complete Tree?
A Binary Tree is complete if all levels are completely filled except possibly the last level and all nodes of last level are as left as possible (Binary Heaps are complete Binary Tree). For a complete Binary Tree, level order traversal is sufficient to store the tree. We know that the first node is root, next two nodes are nodes of next level, next four nodes are nodes of 2nd level and so on.
A Binary Tree is complete if all levels are completely filled except possibly the last level and all nodes of last level are as left as possible (Binary Heaps are complete Binary Tree). For a complete Binary Tree, level order traversal is sufficient to store the tree. We know that the first node is root, next two nodes are nodes of next level, next four nodes are nodes of 2nd level and so on.
If given Binary Tree is Full Tree?
A full Binary is a Binary Tree where every node has either 0 or 2 children. It is easy to serialize such trees as every internal node has 2 children. We can simply store preorder traversal and store a bit with every node to indicate whether the node is an internal node or a leaf node.
A simple solution is to store both Inorder and Preorder traversals. This solution requires requires space twice the size of Binary Tree.A full Binary is a Binary Tree where every node has either 0 or 2 children. It is easy to serialize such trees as every internal node has 2 children. We can simply store preorder traversal and store a bit with every node to indicate whether the node is an internal node or a leaf node.
We can save space by storing Preorder traversal and a marker for NULL pointers.
How much extra space is required in above solution?
If there are n keys, then the above solution requires n+1 markers which may be better than simple solution (storing keys twice) in situations where keys are big or keys have big data items associated with them.
How much extra space is required in above solution?
If there are n keys, then the above solution requires n+1 markers which may be better than simple solution (storing keys twice) in situations where keys are big or keys have big data items associated with them.
Input:
20
/
8
/ \
4 12
/ \
10 14
Output: 20 8 4 -1 -1 12 10 -1 -1 14 -1 -1 -1
void serialize(Node *root, FILE *fp){ // If current node is NULL, store marker if (root == NULL) { fprintf(fp, "%d ", MARKER); return; } // Else, store current node and recur for its children fprintf(fp, "%d ", root->key); serialize(root->left, fp); serialize(root->right, fp);}// This function constructs a tree from a file pointed by 'fp'void deSerialize(Node *&root, FILE *fp){ // Read next item from file. If theere are no more items or next // item is marker, then return int val; if ( !fscanf(fp, "%d ", &val) || val == MARKER) return; // Else create node with this item and recur for children root = newNode(val); deSerialize(root->left, fp); deSerialize(root->right, fp);}One simple optimization is to store a separate bit with every node to indicate that the node is internal or external. This way we don’t have to store two markers with every leaf node as leaves can be identified by extra bit. We still need marker for internal nodes with one child. For example in the following diagram ‘ is used to indicate an internal node set bit, and ‘/’ is used as NULL marker. The diagram is taken from here.
Please note that there are always more leaf nodes than internal nodes in a Binary Tree (Number of leaf nodes is number of internal nodes plus 1, so this optimization makes sense.
http://hehejun.blogspot.com/2015/01/lintcodeserialization-and.html
BFS序列化的表示方法是，按照一层一层的顺序在string尾巴上加字符，null的话用#表示，扫到最后一层为止，也就是说最后一层的地下的null不会出现最后序列化的结果当中。
方法就是BFS的变种，BFS的时候把null也加入list中，那么这个时候就要设定一个变量来判断是不是到了最后一层。反序列的化的时候也是用BFS，注意反序列化的时候最好先按照","spliit成string数组，否则处理字符串的时候不方便处理。值得一提的是BFS用一个list就可以了，比起之前用两个代码会简洁很多。
public String serialize(TreeNode root) { 8 // write your code here 9 StringBuffer res = new StringBuffer(); 10 if (root == null) return res.toString(); 11 LinkedList<TreeNode> queue = new LinkedList<TreeNode>(); 12 queue.offer(root); 13 res.append(root.val); 14 while (!queue.isEmpty()) { 15 TreeNode cur = queue.poll(); 16 if (cur.left != null) queue.offer(cur.left); //add children to the queue 17 if (cur.right != null) queue.offer(cur.right); 18 res.append(","); 19 if (cur.left != null) { 20 res.append(cur.left.val); 21 } 22 else res.append("#"); 23 res.append(","); 24 if (cur.right != null) { 25 res.append(cur.right.val); 26 } 27 else res.append("#"); 28 } 29 int i = res.length()-1; 30 while (i>=0 && res.charAt(i)=='#') { 31 res.deleteCharAt(i); 32 res.deleteCharAt(i-1); 33 i -= 2; 34 } 35 return res.toString(); 36 } 45 public TreeNode deserialize(String data) { 46 // write your code here 47 if (data==null || data.length()==0) return null; 48 String[] arr = data.split(","); 49 int len = arr.length; 50 int count = 0; 51 TreeNode root = new TreeNode(Integer.parseInt(arr[0])); 52 LinkedList<TreeNode> queue = new LinkedList<TreeNode>(); 53 queue.offer(root); 54 count++; 55 while (!queue.isEmpty()) { 56 TreeNode cur = queue.poll(); 57 String left="", right=""; 58 if (count < len) { 59 left = arr[count]; 60 count++; 61 if (!left.equals("#")) { 62 cur.left = new TreeNode(Integer.parseInt(left)); 63 queue.offer(cur.left); 64 } 65 else cur.left = null; 66 } 67 else cur.left = null; 68 69 if (count < len) { 70 right = arr[count]; 71 count++; 72 if (!right.equals("#")) { 73 cur.right = new TreeNode(Integer.parseInt(right)); 74 queue.offer(cur.right); 75 } 76 else cur.right = null; 77 } 78 else cur.right = null; 79 } 80 return root; 81 } 82 }Related: http://massivealgorithms.blogspot.com/2015/10/serialize-and-deserialize-n-ary-tree.html
Read full article from Serialization/Deserialization of a Binary Tree | LeetCode
