题目：请实现两个函数，分别用来序列化和反序列化二叉树。可以根据前序遍历的顺序来序列化二叉树。在遍历二叉树碰到null时，这些null序列化为一个特殊字符'$'。另外，节点的数值之间要用一个特殊字符','隔开。
练习地址
https://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84
https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/
参考答案
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
String Serialize(TreeNode root) {
String result = serialize(root);
return result.substring(0, result.length() - 1);
}
private String serialize(TreeNode node) {
if (node == null) {
return "$,";
}
StringBuilder result = new StringBuilder(node.val + ",");
result.append(serialize(node.left));
result.append(serialize(node.right));
return result.toString();
}
private int mIndex;
TreeNode Deserialize(String str) {
if (str == null || str.length() == 0) {
return null;
}
mIndex = 0;
return deserialize(str.split(","));
}
private TreeNode deserialize(String[] strs) {
if (mIndex >= strs.length || strs[mIndex].equals("$")) {
return null;
}
TreeNode node = new TreeNode(Integer.parseInt(strs[mIndex]));
mIndex++;
node.left = deserialize(strs);
mIndex++;
node.right = deserialize(strs);
return node;
}
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(n)。
