# recursion solution. preorder traversal. add empty node represented in String "n" for 'null' child.

• recursion solution. preorder traversal. add empty node represented in String "n" for 'null' child. Thus every node would have 2 children or 0 children, there's no case that a node has exactly 1 child. Then took advantage of this in deserialization, just like decoding the encoding tree of Huffman tree .

i.e. :
TreeNode node7 = new TreeNode(7, null, null);
TreeNode node8 = new TreeNode(8, null, null);
TreeNode node9 = new TreeNode(9, null, null);
TreeNode node4 = new TreeNode(4, node7, null);
TreeNode node5 = new TreeNode(5, null, node8);
TreeNode node6 = new TreeNode(6, null, node9);
TreeNode node2 = new TreeNode(2, node4, node5);
TreeNode node3 = new TreeNode(3, node6, null);
TreeNode node1 = new TreeNode(1, node2, node3);
BinaryTree tree = new BinaryTree(node1);

serialized string would be "1,2,4,7,n,n,n,5,n,8,n,n,3,6,n,9,n,n,n".

import java.util.concurrent.atomic.AtomicInteger;

public class Codec {

``````// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root == null) {
return "n";
}

return new StringBuffer().append(root.val).append(",")
.append(serialize(root.left)).append(",")
.append(serialize(root.right)).toString();

}

// Decodes your encoded data to tree.
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
return deserialize(data, new AtomicInteger(0));
}

public TreeNode deserialize(String data, AtomicInteger start) {
TreeNode node = null;
if(data == null || data.length() == 0) {
return null;
}
// parse the value from the string,
String nodeVal;
int commaIndex = data.indexOf((int)',', start.intValue());
if(commaIndex == -1) {
nodeVal = data.substring(start.intValue());
} else {
nodeVal = data.substring(start.intValue(), commaIndex);
}

System.out.println("val: " + nodeVal);
start.set(commaIndex + 1);

// if it's null, then return null
if("n".equals(nodeVal)) {
return null;
} else {
// not null
node = new TreeNode(Integer.valueOf(nodeVal).intValue());
node.left = deserialize(data, start);
node.right = deserialize(data, start);
return node;
}
}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.