题目
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
答案
public class Codec {
public String serialize(TreeNode root) {
if(root == null) return "";
String str = Integer.toString(root.val);
if(root.left == null && root.right == null) return str;
if(root.left == null)
str += "()";
else
str += "(" + serialize(root.left) + ")";
if(root.right != null)
str += "(" + serialize(root.right) + ")";
return str;
}
private int find_matching_righ_paren(String data, int left) {
int count = 0;
for(int i = left + 1; i < data.length(); i++) {
if(data.charAt(i) == ')') {
if(count == 0) return i;
else count--;
}
if(data.charAt(i) == '(') count++;
}
return -1;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data.equals("")) return null;
TreeNode t = null;
// Find first left paren
int first_left_paren = data.indexOf('(', 0);
if(first_left_paren == -1) return new TreeNode(Integer.parseInt(data));
else t = new TreeNode(Integer.parseInt(data.substring(0, first_left_paren)));
// Find the right paren that matches first left paren
int first_right_paren = find_matching_righ_paren(data, first_left_paren);
t.left = deserialize(data.substring(first_left_paren + 1, first_right_paren));
// Find first left paren after the above right paren
int second_left_paren = data.indexOf('(', first_right_paren + 1);
if(second_left_paren != -1) {
// Find the right paren that matches the above left paren
int second_right_paren = find_matching_righ_paren(data, second_left_paren);
t.right = deserialize(data.substring(second_left_paren + 1, second_right_paren));
}
return t;
}
}