題目：請實現(xiàn)兩個函數(shù)势就，分別用來序列化和反序列化二叉樹÷雎可以根據(jù)前序遍歷的順序來序列化二叉樹蛋勺。在遍歷二叉樹碰到null時，這些null序列化為一個特殊字符'$'鸠删。另外抱完，節(jié)點的數(shù)值之間要用一個特殊字符','隔開。
練習地址
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)巧娱。
