Serialize and Deserialize Binary Tree
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/
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.
Thoughts
这道题开始想用传统的数组存储法做，即中间结点是root, 左边的是左子树，右边的是右子树。但它的缺点很明显，一来代码写的长，二来所需空间多（即使只存所在位置也无济于事），三来算中点时可能越界。
后来看到高手写的用preorder serialize 和同样调用preorder deserialize, 值得学习。
dfs顺着最左一路捅到底(遇到NULL), backtracking(回栈顶)换边, 继续捅
node/cur是当前, subs[i]是要被插入的, 遇到NULL停止继续搜索.
deserilize当前点和subs[i]的关系:
dfs recursive node即subs[i], node左子树是subs[i+1, ..] 直到遇到NULL, backtracking 紧接着是右子树.
iterative: 当subs[i]不为null, 一直往左下插, 当遇到null意味着要backtracking换边
bfs i和i+1一定是node的左和右.
Code
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
private final String SPLITER = "/";
private final String NULL = "#";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
if (root == null) {
sb.append(NULL).append(SPLITER);
} else {
sb.append(root.val).append(SPLITER);
sb.append(serialize(root.left));
sb.append(serialize(root.right));
}
return sb.toString();
}
int i = -1;
private TreeNode dfs(String[] subs) {
i++;
if (subs[i].equals(NULL)) {
return null;
}
TreeNode node = new TreeNode(Integer.parseInt(subs[i]));
node.left = dfs(subs);
node.right = dfs(subs);
return node;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] subs = data.split(SPLITER);
return dfs(subs);
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));Analysis
时间复杂度O(n), 空间复杂度O(n).
Ver.2
栈内存当前的path, iterative解法的难点在于知道什么时候该backtracing和backtracing到哪里. 由于是二叉树, 有个比较巧妙的解法, 类似在树上做traversal, 维持cur和stack (当前path). 在树上做时是当cur为null时, 让栈顶及父节点帮助改变遍历方向. 这里是用cur来帮助转方向, 让stack只要遇到NULL就pop, 当连遇到两个NULL时意味是叶子, stack中把叶子和它的父节点都pop出来, cur指向父节点. 还有当进入右子节点时, 上一个访问的一定是NULL.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
private final String SPLITER = "/";
private final String NULL = "#";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node == null) {
sb.append(NULL);
} else {
sb.append(node.val);
stack.push(node.right);
stack.push(node.left);
}
sb.append(SPLITER);
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] subs = data.split(SPLITER);
if (subs[0].equals(NULL)) {
return null;
}
//System.out.println(data);
Stack<TreeNode> stack = new Stack<>();
TreeNode root = new TreeNode(Integer.parseInt(subs[0]));
TreeNode cur = root;
stack.push(root);
for (int i = 1; i < subs.length; i++) {
if (!subs[i].equals(NULL)) {
TreeNode node = new TreeNode(Integer.parseInt(subs[i]));
if (subs[i - 1].equals(NULL)) {
cur.right = node;
cur = cur.right;
stack.push(cur);
} else {
cur.left = node;
cur = cur.left;
stack.push(cur);
}
} else if (!stack.isEmpty()) {
cur = stack.pop();
}
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));Ver.3
当是k叉树(k已知)时, 就不能遇到NULL就pop了. 栈依然是path, 栈顶是当前节点. 我们可以用一个map做计数器, 记录每个节点已经访问过了几个边. 当所有边都已经访问过时, pop/backtracing. 由于可能出现连续pop/backtracking的情况, 用一个循环连续检查栈顶.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
private final String SPLITER = "/";
private final String NULL = "#";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node == null) {
sb.append(NULL);
} else {
sb.append(node.val);
stack.push(node.right);
stack.push(node.left);
}
sb.append(SPLITER);
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] subs = data.split(SPLITER);
if (subs[0].equals(NULL)) {
return null;
}
Stack<TreeNode> stack = new Stack<>();
Stack<Integer> meta = new Stack<>();
TreeNode root = new TreeNode(Integer.parseInt(subs[0]));
Map<TreeNode, Integer> map = new HashMap<>();
stack.push(root);
for (int i = 1; i < subs.length; i++) {
while (!stack.isEmpty() && map.containsKey(stack.peek()) && map.get(stack.peek()) == 2) {
stack.pop();
}
TreeNode cur = stack.peek();
if (!subs[i].equals(NULL)) {
TreeNode node = new TreeNode(Integer.parseInt(subs[i]));
if (map.containsKey(cur) && map.get(cur) == 1) {
cur.right = node;
stack.push(node);
} else {
cur.left = node;
stack.push(node);
}
}
map.put(cur, map.getOrDefault(cur, 0) + 1);
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));Ver. 4
BFS
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
private final String SPLITER = "/";
private final String NULL = "#";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node == null) {
sb.append(NULL);
} else {
sb.append(node.val);
queue.offer(node.left);
queue.offer(node.right);
}
sb.append(SPLITER);
}
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] subs = data.split(SPLITER);
if (subs[0].equals(NULL)) {
return null;
}
Queue<TreeNode> queue = new LinkedList<>();
TreeNode root = new TreeNode(Integer.parseInt(subs[0]));
queue.offer(root);
int i = 1;
while (i < subs.length) {
TreeNode node = queue.poll();
if (!subs[i].equals(NULL)) {
node.left = new TreeNode(Integer.parseInt(subs[i]));
queue.offer(node.left);
}
i++;
if (!subs[i].equals(NULL)) {
node.right = new TreeNode(Integer.parseInt(subs[i]));
queue.offer(node.right);
}
i++;
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));Last updated
Was this helpful?