一、前言
本系列文章为《剑指Offer》刷题笔记。
刷题平台：牛客网
书籍下载：共享资源
二、题目
请实现两个函数，分别用来序列化和反序列化二叉树。
1、思路
这道题思路简单，使用前序遍历来序列化和发序列化即可。只要自己写的程序格式对应上即可。可以使用$符号表示NULL，同时每个结点之间，需要添加逗号，即','进行分隔。
直接看代码即可。
2、代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: char* Serialize(TreeNode *root) { if(!root){ return NULL; } string str; SerializeCore(root, str); // 把str流中转换为字符串返回 int length = str.length(); char* res = new char[length+1]; // 把str流中转换为字符串返回 for(int i = 0; i < length; i++){ res[i] = str[i]; } res[length] = '\0'; return res; } TreeNode* Deserialize(char *str) { if(!str){ return NULL; } TreeNode* res = DeserializeCore(&str); return res; } void SerializeCore(TreeNode* root, string& str){ // 如果指针为空，表示左子节点或右子节点为空，则在序列中用#表示 if(!root){ str += '#'; return; } string tmp = to_string(root->val); str += tmp; // 加逗号，用于区分每个结点 str += ','; SerializeCore(root->left, str); SerializeCore(root->right, str); } // 递归时改变了str值使其指向后面的序列，因此要声明为char** TreeNode* DeserializeCore(char** str){ // 到达叶节点时，调用两次，都返回null，所以构建完毕，返回父节点的构建 if(**str == '#'){ (*str)++; return NULL; } // 因为整数是用字符串表示，一个字符表示一位，先进行转换 int num = 0; while(**str != ',' && **str != '\0'){ num = num * 10 + ((**str) - '0'); (*str)++; } TreeNode* root = new TreeNode(num); if(**str == '\0'){ return root; } else{ (*str)++; } root->left = DeserializeCore(str); root->right = DeserializeCore(str); return root; } }; |
更多内容请访问：IT源点
注意：本文归作者所有，未经作者允许，不得转载
