package tree;

import org.junit.Test;

import java.util.LinkedList;

//7. 二叉树的序列化和反序列化

public class Serialize {

public LinkedList<String> split(String string) {

LinkedList<String> linkedList = new LinkedList<>();

String[] strings = string.split("!");

for (String str : strings) {

linkedList.offer(str);

}

return linkedList;

}

/**

* This method will be invoked first, you should design your own algorithm

* to serialize a binary tree which denote by a root node to a string which

* can be easily deserialized by your own "deserialize" method later.

*/

public String serialize(TreeNode root) {

// write your code here

String string = "";

if (root == null) {

return string + "#!";

}

string += root.val + "!";

string += serialize(root.left);

string += serialize(root.right);

return string;

}

/**

* This method will be invoked second, the argument data is what exactly

* you serialized at method "serialize", that means the data is not given by

* system, it's given by your own serialize method. So the format of data is

* designed by yourself, and deserialize it here as you serialize it in

* "serialize" method.

*/

public TreeNode deserialize(String data) {

// write your code here

LinkedList<String> linkedList = split(data);

return deserialize(linkedList);

}

public TreeNode deserialize(LinkedList<String> linkedList) {

// write your code here

TreeNode treeNode = new TreeNode(0);

if (!linkedList.isEmpty()) {

String str = linkedList.poll();

if (str.equals("#")) {

return null;

} else {

treeNode.val = Integer.parseInt(str);

treeNode.left = deserialize(linkedList);

treeNode.right = deserialize(linkedList);

return treeNode;

}

} else {

return null;

}

}

@Test

public void testSerialize() {

deserialize("1!#!2!");

}

}