剑指 Offer 37. 序列化二叉树
首先明确遍历的方式,先序,中序,后序遍历可能对应着多种二叉树,导致序列化后不可逆,通常还是使用层序遍历。
还有就是明确这道题力扣给的测试用例所代表的树到底是什么,例如[5,2,3,null,null,2,4,3,1,null,null,null,null,null,null],需要注意第8,9个元素3,1是第6个元素2的子节点,而不是第4个元素null的子节点,即不是按照满二叉树的标准来生成序列的,因此不能直接使用满二叉树的父节点与子节点的下标关系来做这道题。
层序遍历
- 注意,字符串的操作如果可以使用StringBuilder就尽量使用StringBuilder,会节省很多很多时间
- 新建队列也可以使用Queue queue = new LinkedList<>();
简单说说LinkedList和Queue的区别:
LinkedList实现了Queue接口。Queue接口窄化了对LinkedList的方法的访问权限(即在方法中的参数类型如果是Queue时,就完全只能访问Queue接口所定义的方法 了,而不能直接访问 LinkedList的非Queue的方法),以使得只有恰当的方法才可以使用。
因此,其实用Queue会更规范。
public String serialize(TreeNode root) {
//注意判断根节点是否为空,为空的话直接返回
if(root==null) return "";
StringBuilder s=new StringBuilder("");
//新建一个队列,将根节点入队
LinkedList q=new LinkedList<>();
q.add(root);
//while循环,判断条件是队列是否为空
while(!q.isEmpty()){
TreeNode node=q.poll();
if(node==null){ //节点为空则打印null
s.append("null ");
}else{ //节点不为空则添加左右节点,并打印节点值
//list可以添加空的node,但这个node指向左右孩子以及val值时会报错
q.add(node.left);
q.add(node.right);
s.append(node.val).append(" ");
}
}
return s.toString();
}
反序列化
有点难想明白
public TreeNode deserialize(String data) {
data=data.trim();
String[] a=data.split(" ");
//注意判断data是否为空
if(a[0].equals("")) return null;
TreeNode root=new TreeNode(Integer.parseInt(a[0]));
//i用于遍历data里的数据,任然需要借助队列来构造二叉树
int i=1;
LinkedList q=new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
TreeNode node=q.poll();
//如果不是满二叉树,这种方法就不太行
//int tmp=i*2+1;
//下面的方法算是妙手,还是多看看记住吧,注意i值的变化
//不论节点是否为空,i值都会增加,只有遍历到的数不为空时才将其加入队列
if(!a[i].equals("null")){
node.left=new TreeNode(Integer.parseInt(a[i]));
q.add(node.left);
}
i++;
if(i
node.right=new TreeNode(Integer.parseInt(a[i]));
q.add(node.right);
}
i++;
}
return root;
}
下面为其他人提供的一种反序列化方法,但该方法并不能很好的将数组转化成二叉树,原因就在于前面所说的,力扣通过数组提供的树并不都是按照满二叉树的下标关系来的,因此会出现不完整的转化或者错误的转化
public static TreeNode array2Tree (Integer[] arr){
if (arr.length < 1){
return null;
} else {
TreeNode root = new TreeNode(arr[0]);
int i = 0;
int arrLen = arr.length;
// 用于bfs
Deque queue = new LinkedList<>();
queue.addLast(root);
while (queue.size() > 0){
TreeNode treeNode = queue.removeFirst();
int temp = (i<<1) + 1; //最大的问题就在这一步
if (treeNode != null && temp < arrLen){
if (arr[temp] != null){
treeNode.left = new TreeNode(arr[temp]);
}
temp++;
if (temp < arrLen){
if (arr[temp] != null){
treeNode.right = new TreeNode(arr[temp]);
}
}
queue.addLast(treeNode.left);
queue.addLast(treeNode.right);
}
i++;
}
return root;
}
}



