剑指offer——31序列化二叉树

题目描述

请实现两个函数，分别用来序列化和反序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过某种符号表示空节点（#），以！表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

题解：

　　注意string 到 char*的转换

 class Solution {

 public:

     char* Serialize(TreeNode *root) {

         string str = "";

         preOrder(root, str);

         char *c = new char[str.size() + ];

         strcpy(c, str.c_str());

         return c;

     }

     void preOrder(TreeNode *root, string &str)

     {

         if (root == nullptr)

         {

             str += "#";

             return;

         }

         str += to_string(root->val) + "!";

         preOrder(root->left, str);

         preOrder(root->right, str);

     }

     TreeNode* Deserialize(char *str) {

         string s = str;

         int index = ;

         return createTree(s, index);

     }

     TreeNode* createTree(const string &str, int &index)

     {

         TreeNode* root = nullptr;

         if (str[index] == '#' || index == str.size())

         {

             index++;

             return root;

         }

         string s = "";

         while (str[index] != '!')

             s += str[index++];

         index++;

         root = new TreeNode(atoi(s.c_str()));

         root->left = createTree(str, index);

         root->right = createTree(str, index);

         return root;

     }

 };

巴特西

剑指offer——31序列化二叉树

题目描述

最新文章

热门文章