labuladong 二叉树的序列化
297. 二叉树的序列化与反序列化
序列化
- 前序遍历：（1）注意递归的出口；（2）将前序遍历的根节点数据保存，然后递归左右子树
反序列化
- （1）根据
','把数据分开； - （2）pop出第0个数据，并建立根节点；
- （3）递归剩下的数据
根据树的递归性质，第0个元素就是一棵树的根节点，所以只要将列表的这个元素取出作为根节点，剩下的交给递归去解决即可
- （1）根据
二叉树的遍历：该题也可以用后续遍历及层序遍历解决（不可以用中序，因为中序的话，不知道根节点在哪个位置）
# 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 serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
self.res=''
def dfs(root):
# 递归出口：递归结束的条件，将'None,'保存到结果中
if root==None:
self.res+='None,'
return
# 前序遍历：中
self.res+=str(root.val)+','
## 前序遍历：左右
dfs(root.left)
dfs(root.right)
dfs(root)
return self.res
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
# 先把数据根据','分开
data=data.split(',')
# 递归
def dfs():
# 记录pop出的数据（也是根节点对应数据）
rootData=data.pop(0)
# 递归出口
if rootData=='None':
return None
# 创建根节点
root=TreeNode(int(rootData))
# 递归剩下的数据
root.left=dfs()
root.right=dfs()
return root
return dfs()
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))DFS
序列化
递归的第一步都是特例的处理，因为这是递归的中止条件：如果根节点为空，返回”null“
序列化的结果为：根节点值 + “,” + 左子节点值(进入递归) + “,” + 右子节点值(进入递归)
递归就是不断将“根节点”值加到结果中的过程
反序列化
先将字符串转换成队列（python转换成列表即可）
接下来就进入了递归
i. 弹出左侧元素，即队列出队
ii. 如果元素为“null”，返回null（python返回None）
iii. 否则，新建一个值为弹出元素的新节点
iv. 其左子节点为队列的下一个元素，进入递归；右子节点为队列的下下个元素，也进入递归
v. 递归就是不断将子树的根节点连接到父节点的过程
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
if not root:
return 'None'
return str(root.val) + ',' + str(self.serialize(root.left)) + ',' + str(self.serialize(root.right))
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
def dfs(dataList):
val = dataList.pop(0)
if val == 'None':
return None
root = TreeNode(int(val))
root.left = dfs(dataList)
root.right = dfs(dataList)
return root
dataList = data.split(',')
return dfs(dataList)
前序、后序、层序都能够很好的找到根节点，而且不同于一般构造二叉树的问题，此处将空指针的地方指出，相当于比较完整的给出了树的结构。
反序列化时，在确定根节点后，紧接着确定某一子树，对当前子树采用递归，形成了相同的问题，类似于序列化过程中的递归问题。
反序列化中值得注意的是，前序是利用序列化结果，依次从前往后构造节点，类似于队列；后序依次从后往前，类似于栈；
中序时，由于无法从序列化结果中找到根节点位置，也就无法准确划分左右子树，无法形成递归的结构，这种方式不能反序列化！
层序遍历思路类似，相对要麻烦一点点点，拿新结点一层一层的往后面接，这里可以考虑直接用vector加上索引（也可以用queue，但是vector访问简洁一点）
c++没有像python那样的split()函数，所以要自己写该函数来处理数据
class Codec {
private:
string res="";
public:
// 序列化
// 前序遍历
void dfs(TreeNode* root){
// 递归出口
if (root==nullptr){
res+="NULL,";
return;
}
// 前序：中
res+=(to_string(root->val))+",";
// 前序：左右
dfs(root->left);
dfs(root->right);
}
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
dfs(root);
res.pop_back();// 去掉结尾的","
return res;
}
///////////////////////////////////////////////////////
//反序列化
// 将string类的数据根据','进行split
queue<string> split(string& data){
queue<string> q;
int start=0; // 如：123,456,789中，start表示每个数字开始的地方
// 注意这里的 i <= data.size() 和 if (i == data.size() ||data[i]==',')
// 1,2,3,4,5,6 最后的6后面没有逗号，但我们要把6push进去，因此要 取等于号，且if里面有 ||（或）
for (int i = 0; i <= data.size(); ++i) {
if (i == data.size() ||data[i]==','){
q.push(data.substr(start,i-start));
start=i+1;
}
}
return q;
}
// 对queue<string>类型的数据用递归
TreeNode* deserializeQueue(queue<string>& q){
string rootData=q.front();
q.pop(); // 队列的pop是pop最开头的元素
if (rootData=="NULL"){
return nullptr;
}
TreeNode* root=new TreeNode(stoi(rootData));
root->left=deserializeQueue(q);
root->right=deserializeQueue(q);
return root;
}
// Decodes your encoded data to tree.
// 调用上面的split函数和deserializeQueue函数
TreeNode* deserialize(string data) {
queue<string> Q= split(data);
return deserializeQueue(Q);
}
};
// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));
