2014-05-02 00:59

原题：

Given a normal binary tree, write a function to serialize the tree into a string representation (returning the string), and also a function to deserialize a serialized string into the original binary tree.

题目：给定一棵二叉树，请设计序列化和反序列化的方法。

解法：我的方法是使用前序遍历来进行序列化，其中大括号"{}"包含了数据序列，用“#”表示空指针。反序列化的思路则相反。

代码：

1 // http://www.careercup.com/question?id=5729456584916992 2 #include 
     
       3 #include 
      
        4 #include 
       
         5 using namespace std; 6  7 struct TreeNode { 8     int val; 9     TreeNode *left;10     TreeNode *right;11     TreeNode(int _val = 0): val(_val), left(nullptr), right(nullptr) {};12 };13 14 class BinaryTreeSerializer {15 public:16     string serialize(TreeNode *root) {17         string res = "{
    ";18         19         // preorder traversal20         serializeTraversal(root, res);21         res[res.length() - 1] = '}';22         23         return res;24     };25     26     TreeNode *deserialize(string s) {27         vector
        
          data;28         int i, j, len;29         30         len = (int)s.length();31         i = 1;32         while (true) {33             j = i + 1;34             while (s[j] != ',' && s[j] != '}') {35                 ++j;36             }37             data.push_back(s.substr(i, j - i));38             i = j + 1;39             if (i >= len) {40                 break;41             }42         }43         44         int iter = 0;45         TreeNode *root = nullptr;46         47         // preorder traversal48         deserializeTraversal(data, root, iter);49         50         return root;51     };52 private:53     static char ss[10];54     55     void serializeTraversal(TreeNode *root, string &res) {56         if (root == nullptr) {57             res += "#,";58         } else {59             sprintf(ss, "%d", root->val);60             res += string(ss);61             res.push_back(',');62             serializeTraversal(root->left, res);63             serializeTraversal(root->right, res);64         }65     };66     67     void deserializeTraversal(vector
         
           &data, TreeNode *&root, int &iter) {68         ++iter;69         if (data[iter - 1] == "#") {70             root = nullptr;71         } else {72             int val;73             74             sscanf(data[iter - 1].c_str(), "%d", &val);75             root = new TreeNode(val);76             deserializeTraversal(data, root->left, iter);77             deserializeTraversal(data, root->right, iter);78         }79     };80 };