序列化二叉树
class Solution {
public:
char* Serialize(TreeNode *root) {
if (!root)
return nullptr;
string resStr; //存放结果
serializeTree(root, resStr);
char *res = new char[resStr.length() +1]; strcpy(res, const_cast<char*>(resStr.c_str())); return res; } TreeNode* Deserialize(char *str) { TreeNode *root = nullptr; if (!str) return root; int length = strlen(str); int index = 0; DeserializeTree(&root, str, length - 1, index); return root; }
private:
//序列化递归
void serializeTree(TreeNode* root, string &str)
{
if (!root)
{
str = str + "#!";
return;
}
string newChar = to_string(root->val);
str += newChar;
str += '!';
//if (root->left) //错误1:递归里面会有 空节点的处理!!
serializeTree(root->left, str);
//if (root->right)
serializeTree(root->right, str);
}
//反序列化递归建树 void DeserializeTree(TreeNode **pRoot, char*strChar, int length, int &index) { string str; //该节点存放的数值的字符表达 while (strChar[index] != '!') { str += strChar[index++]; }//循环结束 index 指向 ’!' if (str == "#") //若为空节点 { index++; return; } else { //若不为空结点 int val = atoi(str.c_str()); *pRoot = new TreeNode(val); (*pRoot)->val = val; index++; if (index <= length) { DeserializeTree(&(*pRoot)->left, strChar, length, index); } if (index <= length) { DeserializeTree(&(*pRoot)->right, strChar, length, index); } } }
};