【树】二叉树的序列化与反序列化

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Codec {
11 public:
12     
13     // Encodes a tree to a single string.
14     // 先序遍历
15     string serialize(TreeNode* root) 
16     {
17         if (NULL == root)
18         {
19             return "null,";
20         }
21         
22         return std::to_string(root->val) + "," + serialize(root->left) + serialize(root->right);    
23     }
24 
25     // Decodes your encoded data to tree.
26     TreeNode* deserialize(string data) 
27     {
28         queue<std::string> q;
29         string s;
30         
31         for (int i = 0; i < data.size(); i++)
32         {
33             if (data[i] == ‘,‘)
34             {
35                 q.push(s);
36                 s = "";
37                 continue;
38             }
39             
40             s += data[i];
41         }
42        
43         if (s.size() != 0)
44         {
45             q.push(s);
46         }
47         
48         return deserializehepler(q);
49     }
50     
51     TreeNode* deserializehepler(queue<std::string> &q)
52     {
53         string s = q.front();
54         q.pop();
55         if (s == "null")
56         {
57             return NULL;
58         }
59         
60         TreeNode *root = new TreeNode(stoi(s));
61         root->left = deserializehepler(q);
62         root->right = deserializehepler(q);
63         
64         return root;  
65     }
66 };
67 
68 // Your Codec object will be instantiated and called as such:
69 // Codec codec;
70 // codec.deserialize(codec.serialize(root));