LeetCode-面试题37-序列化二叉树
# LeetCode-面试题37-序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树。
示例：
你可以将以下二叉树：
1
/ \
2 3
/ \
4 5
序列化为 "[1,2,3,null,null,4,5]"# 解题思路
BFS+位置指针(队列、递归2种解法)：
队列：
- 序列化的过程是一个典型的BFS层序遍历，由于返回的要求是String类型，所以在遍历的同时加上字符串拼接即可
- 反序列化的过程，利用一个队列按层构建二叉树，并使用index指针记录节点temp的左子节点和右子节点。每构建一个节点，index就向右移动1位，只有当节点不为空时，左右节点的构建才有效。为空时index++会跳过值为null的节点
递归：
注意：递归序列化出来的序列和队列方式结果不同，递归返回的列表数据更像DFS遍历的结果，虽然两者序列化和反序列化的方式不同，但不影响构建结果。即怎么序列化，就怎么反序列化
初始化：res列表，index指针
序列化递归：
- 判断头节点是否为空，为空则直接返回空列表
- 否则开始序列化递归，序列化递归过程如下：
**终止条件：**当遍历到左/右子节点为空时，res添加null字符，返回
**递推：**res添加root节点值，开启左子树遍历
self.serhelper(root.left)，之后开启右子树遍历self.serhelper(root.right)
反序列化递归：
- 判断头节点是否为空，为空则直接返回空列表
- 否则开始反序列化递归，过程如下：
**终止条件：**index位置为null，说明此位置是空节点，index后移一位，返回None
**递推：**新建Node，index指针后移指向左节点，开启左右子树递归
node.left = self.deshelper(data)和node.right = self.deshelper(data)
# Java代码
/**
* 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) {
if(root==null) return "[]";
StringBuilder res = new StringBuilder("[");
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
TreeNode temp = queue.poll();
if(temp!=null){
res.append(temp.val+",");
queue.add(temp.left);
queue.add(temp.right);
}
else
res.append("null,");
}
res.deleteCharAt(res.length()-1);
res.append("]");
return res.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data.equals("[]")) return null;
String[] origin = data.substring(1,data.length()-1).split(",");
TreeNode root = new TreeNode(Integer.parseInt(origin[0]));
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int index = 1;
while(!queue.isEmpty()){
TreeNode temp = queue.poll();
if(!origin[index].equals("null")){
temp.left = new TreeNode(Integer.parseInt(origin[index]));
queue.add(temp.left);
}
index++;
if(!origin[index].equals("null")){
temp.right = new TreeNode(Integer.parseInt(origin[index]));
queue.add(temp.right);
}
index++;
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));# Python代码
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
def __init__(self):
self.res = []
self.index = 0
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
if not root: return []
self.serhelper(root)
return self.res
def serhelper(self,root):
if not root:
self.res.append("null")
return
self.res.append(root.val)
self.serhelper(root.left)
self.serhelper(root.right)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
if not data: return []
return self.deshelper(data)
def deshelper(self,data):
if data[self.index] == "null":
self.index+=1
return None
node = TreeNode(data[self.index])
self.index+=1
node.left = self.deshelper(data)
node.right = self.deshelper(data)
return node
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-04-26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读