[Leetcode] Serialize and Deserialize Binary Tree, Solution

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

[Thoughts]

这题纯粹是一道实现题，没有难点。看Code。



[Code]

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:    string serialize(TreeNode* root) {  
15:      stringstream ss;  
16:      serializeImpl(root, ss);  
17:      return ss.str();  
18:    }  
19:    
20:    // Decodes your encoded data to tree.  
21:    TreeNode* deserialize(string data) {  
22:      std::istringstream ss(data);  
23:      return deserializeImpl(ss);  
24:    }  
25:      
26:    void serializeImpl(TreeNode* root, stringstream& ss) {  
27:      if(root == NULL) {  
28:        ss<<"#,";  
29:        return;  
30:      }  
31:        
32:      ss << root->val << ",";  
33:      serializeImpl(root->left, ss);  
34:      serializeImpl(root->right, ss);  
35:    }  
36:      
37:    TreeNode* deserializeImpl(istringstream & ss) {  
38:      std::string token;  
39:    
40:      std::getline(ss, token, ',');  
41:        
42:      if(token == "#") {  
43:        return NULL;  
44:      }  
45:        
46:      TreeNode* root = new TreeNode(stoi(token));  
47:        
48:      root->left = deserializeImpl(ss);  
49:      root->right = deserializeImpl(ss);  
50:      return root;  
51:    }  
52:      
53:      
54:  };  
55:    
56:  // Your Codec object will be instantiated and called as such:  
57:  // Codec codec;  
58:  // codec.deserialize(codec.serialize(root));