解题思路
序列化时,可以通过各种遍历方法,例如层序遍历、递归遍历对二叉树进行遍历,遍历过程中将每个节点的值拼接到字符串中,注意每个节点之间用一个标识符隔开,例如,
,这是为了防止节点的值超过个位数。
反序列化则根据序列化的过程进行相应的解码,不同的反序列化方式有不同的技巧,下面分别使用层序遍历和先序遍历两种方法进行求解。
解法一:层序遍历
- 序列化:通过队列进行遍历,然后生成序列化的字符串,比较常规。
- 反序列化:稍微有点难度。首先对
res
按照,
进行切分得到String数组strs
,每个位置表示一个节点的值。和序列化一样,也需要使用一个队列进行操作,注意每次需要取数组strs
中的两个元素,即构建当前节点的左右子树,然后分别把左右子树加入队列中。
import java.util.*;
public class Solution {
String Serialize(TreeNode root) {
String str = "";
if (root == null)
return str;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
str += root.val + ",";
while (!queue.isEmpty()) {
TreeNode top = queue.poll();
if (top.left == null)
str += "#";
else {
queue.add(top.left);
str += top.left.val;
}
str += ',';
if (top.right == null)
str += "#";
else {
queue.add(top.right);
str += top.right.val;
}
str += ',';
}
return str;
}
TreeNode Deserialize(String str) {
if (str.length() == 0)
return null;
int i = 1;
String strList[] = str.split(",");
TreeNode root = new TreeNode(Integer.parseInt(strList[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode top = queue.poll();
if (strList[i].equals("#"))
top.left = null;
else {
top.left = new TreeNode(Integer.parseInt(strList[i]));
queue.add(top.left);
}
i++;
if (strList[i].equals("#"))
top.right = null;
else {
top.right = new TreeNode(Integer.parseInt(strList[i]));
queue.add(top.right);
}
i++;
}
return root;
}
}
解法二:先序遍历
- 序列化:定义全局字符串
res
,递归的时候记录遍历到的节点值,遍历完一个节点后,在其后加,
标识符。 - 反序列化:稍微有点难度。首先对
res
按照,
进行切分得到String数组strs
,每个位置表示一个节点的值。定义全局变量ind
,用来记录当前遍历到strs
的位置,如果当前位置是#
,表示为空,直接返回null
;否则新建一个节点node
,并递归构建其左右子树,注意,在递归前判断数组是否越界,如果inds++
后等于strs
的长度,则表明已经遍历完数组,此时返回node
(注意数组越界的判断不能放在开头,否则会写不下去,因为不知道返回什么了)
import java.util.*;
public class Solution {
public String res = "";
public int ind = 0;
String Serialize(TreeNode root) {
if (root == null) {
res += "#,";
return res;
}
res += root.val + ",";
Serialize(root.left);
Serialize(root.right);
return res;
}
TreeNode deserialize(String[] strs) {
if (strs[ind].equals("#")) {
ind++;
return null;
}
TreeNode node = new TreeNode(Integer.parseInt(strs[ind]));
ind++;
if (ind >= strs.length)
return node;
node.left = deserialize(strs);
node.right = deserialize(strs);
return node;
}
TreeNode Deserialize(String str) {
String[] strs = str.split(",");
return deserialize(strs);
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)