今日算法之_93_二叉树的序列化与反序列化
前言
Github:https://github.com/HealerJean
1、二叉树的序列化与反序列化
二叉树的序列化与反序列化
1.1、解题思路
就是一个递归算法的二叉树先序遍历,只不过是将空节点变成null字符串存储
1.2、算法
public String serialize(TreeNode root) {
StringBuilder str = new StringBuilder();
mySeri(root, str);
return str.toString();
}
public TreeNode deserialize(String data) {
List<String> list = new LinkedList<>(Arrays.asList(data.split(",")));
return myDeSeri(list);
}
void mySeri(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append("null,");
return;
}
sb.append(root.val + ",");
mySeri(root.left, sb);
mySeri(root.right, sb);
}
public TreeNode myDeSeri(List<String> list) {
TreeNode root;
String strValue = list.get(0);
if ("null".equals(strValue)) {
list.remove(0);
return null;
} else {
int val = Integer.valueOf(strValue);
root = new TreeNode(val);
list.remove(0);
// 当返回null的时候会结束
root.left = myDeSeri(list);
root.right = myDeSeri(list);
}
return root;
}
public TreeNode initTreeNode() {
TreeNode treeNode4 = new TreeNode(4, null, null);
TreeNode treeNode3 = new TreeNode(3, null, null);
TreeNode treeNode2 = new TreeNode(2, treeNode3, treeNode4);
TreeNode treeNode5 = new TreeNode(5, null, null);
TreeNode root = new TreeNode(1, treeNode2, treeNode5);
return root;
}
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
TreeNode(int x, TreeNode left, TreeNode right) {
this.val = x;
this.left = left;
this.right = right;
}
}
1.3、测试
@Test
public void test() {
System.out.println(serialize(initTreeNode()));
}