37
1. 描述
请实现两个函数，分别用来序列化和反序列化二叉树。
2. 题解
n = i_pushed.size()
时间复杂度: O(n)
空间复杂度: O(n)
我们可以将一棵树保存前序和中序遍历（或中序和后序），然后重建二叉树，但是这要求树中所有节点的值不一样，题目并没有给出这样的保证。
因此我们可以将其按照先序遍历的形式保存节点，空节点用一个特殊符号替代，遍历到特殊符号时就知道遍历到了空节点，到了递归的边界。
class Codec
{
private:
TreeNode* deserialize(stringstream &i_stream)
{
string node;
i_stream >>node;
if(node == string("#")) // nullptr
{
return nullptr;
}
else
{
int value = stoi(node);
auto root = new TreeNode(value);
root->left = deserialize(i_stream);
root->right = deserialize(i_stream);
return root;
}
}
public:
// Encodes a tree to a single string.
// string serialize(TreeNode* root)
string serialize(TreeNode *i_root)
{
if(!i_root) return string("# ");
string nodes = to_string(i_root->val) + string(" ");
return nodes + serialize(i_root->left) + serialize(i_root->right);
}
// Decodes your encoded data to tree.
// TreeNode* deserialize(string data)
TreeNode* deserialize(string i_data)
{
stringstream stream(i_data);
return deserialize(stream);
}
};