主要有String 图 还有二叉树 的 二叉树的遍历化解 要结合几种遍历 方式 可以考虑层序遍历(BFS) 或者Pre-order 在还原的时候建立相应的结构可以还原
297. Serialize and Deserialize Binary Tree
I. 一种做法是用BFS 然后还原 每个点之间用”，“ 分离 Null也要写入 还原的时候也是加入到Queue里 然后
依次衔接构建(如果不清除画图)
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
if(root == null)return "";
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.add(root);
String delim = "";
while(!q.isEmpty()){
TreeNode t = q.remove();
sb.append(delim);
if(t != null){
sb.append(String.valueOf(t.val));
q.add(t.left);
q.add(t.right);
}
else{
sb.append("null");
}
delim = ",";
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data){
String[] arr = data.split(",");
int len = arr.length;
if(data == null||data.length()==0)return null;
Queue<TreeNode> q = new LinkedList<TreeNode>();
TreeNode root = new TreeNode(Integer.parseInt(arr[0]));
q.add(root);
int pos = 1;
while(!q.isEmpty()&& pos < len){
TreeNode cur = q.remove();
cur.left = createNode(arr[pos++]);
if(cur.left != null) q.add(cur.left);
if (pos < len){
cur.right = createNode(arr[pos++]);
if (cur.right != null) q.add(cur.right);
}
}
return root;
}
public TreeNode createNode(String val)
{
if( val.equals("null") ) return null;
return new TreeNode(Integer.parseInt(val));
}
}
II 还有就是DFS的写法
写了一个Pre Order的recursive的版本 发现好多问题 一个是递归里面 用Object作为参数 注意什么时候增加index
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
// write your code here
StringBuilder bd = new StringBuilder();
helper(root,bd);
bd.setLength(bd.length() - 1);
return bd.toString();
}
public void helper(TreeNode root,StringBuilder bd){
if(root == null){
bd.append("#").append(",");
return;
}
bd.append(root.val).append(",");
helper(root.left,bd);
helper(root.right,bd);
}
/**
* 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) {
String[] A = data.split(",");
int[] arr = new int[]{0};
return helper(A,arr);
}
public TreeNode helper(String[] A,int[] arr){
if(arr[0] == A.length) return null;
String cur = A[arr[0]];
//why we don't put the increase after this line? because it acts like a global one
//and may lose the chance to increase after that
if(cur.equals("#")){
arr[0]++;
return null;
}
TreeNode node = new TreeNode(Integer.parseInt(cur));
arr[0]++;
node.left = helper(A,arr);
node.right = helper(A,arr);
return node;
}
}
449. Serialize and Deserialize BST
一般的解法也可以试用 只是我们可以形成PreOrder 然后Sort一下得到Inorder序列 然后通过这两个序列 借用以前的做法
- Construct Binary Tree from Preorder and Inorder Traversal
*** Serialize and Deserialize a Graph
Onsite没有写出来 自己下来写了一下 代码没有测试过 这里用的图的表示方法是用邻接表 然后我给每个节点加了一个Unique Number 每个节点处理完之后有一个“*” 分隔
1 , A , 2, B, 4, L, * , 9, K, 1, B
public class GraphNode{
public List<GraphNode> neighbor;
public String name;
public GraphNode(String name){
neighbor = new ArrayList<GraphNode>();
this.name = name;
}
}
public class Solution{
//Given a list of GraphNode Serialize it to String
public String encode(List<GraphNode> list){
int n = list.size();
StringBuilder bd = new StringBuilder();
HashMap<GraphNode,Integer> map = new HashMap<GraphNode,Integer>();
//Build a map between the unique identifier and the Graph Node
for(int i = 0;i < n;i++){
map.put(list.get(i),i);
}
//Use the delim to seperate each node in the list with each other
String delim = "";
//
for(GraphNode cur: list){
bd.append(delim);
bd.append(map.get(cur)).append(",");
bd.append(cur.name).append(",");
//Seperate the node with its neighbors
for(GraphNode adj: cur.neighbor){
bd.append(map.get(adj)).append(",");
bd.append(cur.name).append(",");
}
bd.append("*");
delim = ",";
}
return bd.toString();
}
//Given a String and convert it back to Graph
public List<GraphNode> decode(String s){
String[] arr = s.split(",");
int len = arr.length;
List<GraphNode> result = new ArrayList<GraphNode>();
//Avoid building the same node over again
HashMap<String,GraphNode> map = new HashMap<String,GraphNode>();
int i = 0;
while(i < len){
//the first two element serves as the current GraphNode wait to add its neignbors
if(!map.containsKey(arr[i])){
GraphNode newNode = new GraphNode(arr[i+1]);
map.put(arr[i],newNode);
}
GraphNode cur = map.get(arr[i]);
i = i + 2;
//Add the neignbors
while(i < len && !arr[i].equals("*")){
if(!map.containsKey(arr[i])){
GraphNode node = new GraphNode(arr[i+1]);
map.put(arr[i],node);
}
cur.neignbors.add(map.get(arr[i]));
//deal with next pair
i = i + 2;
}
i++;
}
//In the final round add all the GraphNode to the final result list
for(GraphNode graph: map.values()){
result.add(graph);
}
return result;
}
}
还有一种用矩阵表示Graph的做法 还没有写
535. Encode and Decode TinyURL
看到别人的一个解法 是用string本身的hashcode然后加上nanotime 储存在哈希表里面
建立两个映射 以便于以后的查找 只是industry里面的都是这么做的吗？