Version #5 Byte Manipulation
这个方法是把Integer直接变成string给改成byte 表示法，可以压缩space
String ->
-2^31 = -2147483648 -> 11 chars
https://www.javamex.com/tutorials/memory/string_memory_usage.shtml
Byte -> 0xFFFFFFFF
4 bytes
No string-integer conversion needed
如果是 int -> byte[] -> char[] 的话，转换回来的时候
如果不
// return (int) ((data[0] & 0xff) << 24)
// | ((data[1] & 0xff) << 16)
// | ((data[2] & 0xff) << 8)
// | (data[3] & 0xff);
就会出错
然而如果直接 int -> char[]就不需要考虑这个问题，因为在int -> char[] 的时候已经
(char)((x >> 24) & 0xff),
(char)((x >> 16) & 0xff),
(char)((x >> 8) & 0xff),
(char)(x & 0xff)
了
99.15 %
public class Codec {
private char NULL_VALUE = '0';
private char NOT_NULL_VALUE = '1';
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
seHelper(root, sb);
return sb.toString();
}
private void seHelper(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append(NULL_VALUE);
return;
}
char[] array = int2Bytes(node.val);
sb.append(NOT_NULL_VALUE).append(array[0]).append(array[1]).append(array[2]).append(array[3]);
seHelper(node.left, sb);
seHelper(node.right, sb);
}
private char[] int2Bytes(int x) {
return new char[]{
(char)((x >> 24) & 0xff),
(char)((x >> 16) & 0xff),
(char)((x >> 8) & 0xff),
(char)(x & 0xff)
};
}
// Decodes your encoded data to tree.
private int index;
public TreeNode deserialize(String data) {
index = 0;
return deHelper(data.toCharArray());
}
private TreeNode deHelper(char[] data) {
if (data[index++] == NULL_VALUE) {
return null;
}
TreeNode node = new TreeNode(bytes2Int(new char[]{
data[index],
data[index + 1],
data[index + 2],
data[index + 3]
}));
index += 4;
node.left = deHelper(data);
node.right = deHelper(data);
return node;
}
private int bytes2Int(char[] data) {
return (int) (data[0] << 24)
| (data[1] << 16)
| (data[2] << 8)
| data[3];
}
}
Version #3 Iteration with Stack
二刷
看一刷的不知道自己在写什么。。。为什么需要一个boolean来判断是不是left？
Stack 加的时候注意是先左后右
Stack deserialize的时候，都是向左走到底，然后向右跳一个
39.88 %
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return null;
}
StringBuilder sb = new StringBuilder();
Deque<TreeNode> stack = new LinkedList<>();
stack.addFirst(root);
while (!stack.isEmpty()) {
TreeNode curr = stack.removeFirst();
if (curr == null) {
sb.append("#,");
} else {
sb.append(curr.val + ",");
stack.addFirst(curr.right);
stack.addFirst(curr.left);
}
}
System.out.println(sb.toString());
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null || data.length() == 0) {
return null;
}
String[] strs = data.split(",");
Deque<TreeNode> stack = new LinkedList<>();
int pointer = 0;
if (strs.length == 0 || strs[pointer].equals("#")) {
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(strs[0]));
TreeNode curr = root;
stack.addFirst(root);
pointer++;
while (pointer < strs.length) {
while (curr != null) {
stack.addFirst(curr);
curr.left = strs[pointer].equals("#") ? null : new TreeNode(Integer.valueOf(strs[pointer]));
pointer++;
curr = curr.left;
}
curr = stack.removeFirst();
curr.right = strs[pointer].equals("#") ? null : new TreeNode(Integer.valueOf(strs[pointer]));
pointer++;
curr = curr.right;
}
return root;
}
}
一刷
Iteration desirialization 好难啊，写了好久好久好久
stack里面放的是已经连完左节点但是等待右subtree的点
curr代表的是当下等待连左节点的点
如果遇到null
1st -> 证明当前curr的left subtree是null
当前curr已经是Left most node
开始往外pop
2nd -> 在pop round，pop出的点是waiting for its right subtree
此时遇到null 证明当前点的right subtree是NULL
直接继续pop
37.48 %
public class Codec {
private static final String DIVIDER = "/";
private static final String NULL = "null";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return null;
StringBuilder sb = new StringBuilder();
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
if (curr != null) {
sb.append(curr.val);
sb.append(DIVIDER);
stack.push(curr);
curr = curr.left;
} else {
sb.append(NULL + DIVIDER);
curr = stack.pop();
curr = curr.right;
}
}
sb.deleteCharAt(sb.length() - 1);
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null) return null;
String[] strs = data.trim().split(DIVIDER);
int index = 0;
TreeNode root = new TreeNode(Integer.valueOf(strs[index++]));
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
stack.push(curr);
int n = strs.length;
// Nodes in stack -> waiting for their right subtree
// curr -> waiting for its left subtree
while (index < n) {
while (index < n && !strs[index].equals(NULL)) {
curr.left = new TreeNode(Integer.valueOf(strs[index++]));
curr = curr.left;
stack.push(curr);
}
// Top nodes left subtree is null, get the next candidate node
while (index < n && strs[index].equals(NULL)) {
curr = stack.pop();
index++;
}
// strs[index] is not NULL
if (index < n) {
curr.right = new TreeNode(Integer.valueOf(strs[index++]));
curr = curr.right;
stack.push(curr);
}
}
return root;
}
}
Version #4 Recursion DFS
Pre-Order Traversal
注意pointer是一个global变量，每一次recursion的当前层负责给pointer + 1
二刷
94.28 %
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
seHelper(root, sb);
return sb.toString();
}
private void seHelper(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append("#,");
return;
}
sb.append(node.val + ",");
seHelper(node.left, sb);
seHelper(node.right, sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null || data.length() == 0) {
return null;
}
String[] strs = data.split(",");
int[] pointer = new int[]{0};
return deHelper(strs, pointer);
}
private TreeNode deHelper(String[] strs, int[] pointer) {
if (strs[pointer[0]].equals("#")) {
pointer[0]++;
return null;
}
TreeNode node = new TreeNode(Integer.valueOf(strs[pointer[0]]));
pointer[0]++;
node.left = deHelper(strs, pointer);
node.right = deHelper(strs, pointer);
return node;
}
}
Version #1 jiuzhang Version BFS with Queue
二刷
49.87 %
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
Queue<TreeNode> que = new LinkedList<>();
if (root == null) {
return null;
}
que.offer(root);
while (!que.isEmpty()) {
TreeNode curr = que.poll();
if (curr == null) {
sb.append("#,");
} else {
sb.append(curr.val + ",");
que.offer(curr.left);
que.offer(curr.right);
}
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null || data.length() == 0) {
return null;
}
String[] strs = data.split(",");
Queue<TreeNode> que = new LinkedList<>();
if (strs.length == 0) {
return null;
}
int pointer = 0;
TreeNode root = new TreeNode(Integer.valueOf(strs[pointer++]));
que.offer(root);
while (!que.isEmpty()) {
TreeNode curr = que.poll();
TreeNode left = null;
if (!strs[pointer].equals("#")) {
left = new TreeNode(Integer.valueOf(strs[pointer]));
que.offer(left);
}
pointer++;
curr.left = left;
TreeNode right = null;
if (!strs[pointer].equals("#")) {
right = new TreeNode(Integer.valueOf(strs[pointer]));
que.offer(right);
}
pointer++;
curr.right = right;
}
return root;
}
}
一刷
49.35 %
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return "{}";
ArrayList<TreeNode> que = new ArrayList<>();
que.add(root);
TreeNode curr = null;
for (int i = 0; i < que.size(); i++) {
curr = que.get(i);
if (curr == null) continue;
que.add(curr.left);
que.add(curr.right);
}
StringBuilder sb = new StringBuilder();
sb.append("{");
curr = que.get(0);
int index = 1;
sb.append(String.valueOf(curr.val));
while (index < que.size()) {
curr = que.get(index);
index++;
sb.append(",");
if (curr == null) sb.append("#");
else sb.append(String.valueOf(curr.val));
}
sb.append("}");
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.equals("{}")) {
return null;
}
String[] vals = data.substring(1, data.length() - 1).split(",");
ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
queue.add(root);
int index = 0;
boolean isLeftChild = true;
for (int i = 1; i < vals.length; i++) {
if (!vals[i].equals("#")) {
TreeNode node = new TreeNode(Integer.parseInt(vals[i]));
if (isLeftChild) {
queue.get(index).left = node;
} else {
queue.get(index).right = node;
}
queue.add(node);
}
if (!isLeftChild) {
index++;
}
isLeftChild = !isLeftChild;
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
Version #2
自己改进了一下感觉比上个方法简洁一点 就是传统地用queue
上个方法里面用ArrayList作为Queue然后用get(index) 来代替queue.poll()感觉也挺有意思的
注意！string == "#"是不对的 必须string.equals("#");
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return "";
StringBuilder sb = new StringBuilder();
Queue<TreeNode> que = new LinkedList<>();
que.add(root);
TreeNode curr = null;
while (!que.isEmpty()) {
curr = que.poll();
if (curr == null) {
sb.append("#,");
continue;
} else {
sb.append(String.valueOf(curr.val));
sb.append(",");
}
que.add(curr.left);
que.add(curr.right);
}
char c = sb.charAt(sb.length() - 1);
do {
sb.deleteCharAt(sb.length() - 1);
c = sb.charAt(sb.length() - 1);
} while (c == '#' || c == ',');
//System.out.println(sb.toString());
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == "") return null;
String[] vals = data.split(",");
Queue<TreeNode> que = new LinkedList<>();
TreeNode root = new TreeNode(Integer.valueOf(vals[0]));
que.add(root);
TreeNode curr = null;
boolean isLeft = true;
for (int index = 1; index < vals.length; index++) {
if (vals[index].equals("#")) {
curr = null;
} else {
curr = new TreeNode(Integer.valueOf(vals[index]));
que.add(curr);
}
if (isLeft) {
que.peek().left = curr;
} else {
que.poll().right = curr;
}
isLeft = !isLeft;
}
return root;
}
}
No comments:
Post a Comment