37. serialized binary tree

The finger of the sword Offer 37. Serialize binary tree

Ideas ： Sequence traversal

serialize

• initialization ： queue queue, result res
• Remove the node from the queue ：
  • If the node is empty , Print string "null,"
  • If the node is not empty , Print corresponding numbers , Add the left and right child nodes queue
• Return value ：res

deserialize

• initialization ： queue queue, The root node root
• Get the current node from the queue cur
  • Traversal string , If the current value is not empty , structure cur->left, And join the queue
  • Traversal string , If the current value is not empty , structure cur->right, And join the queue
• Return root node

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        string ans;
        while(q.size()){
            TreeNode* cur=q.front();
            q.pop();
            if(cur==nullptr){
                ans+="null,";
            }
            else{
                ans+=to_string(cur->val)+",";
                q.push(cur->left);
                q.push(cur->right);
            }
        }
        return ans;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int i=0,j=0;
        while(j<data.size()&&data[j]!=',')++j;
        string s=data.substr(i,j-i);
        if(s=="null") return nullptr;
        TreeNode* root=new TreeNode(stoi(s));
        queue<TreeNode*> q;
        q.push(root);
        while(q.size()){
            TreeNode* cur=q.front();
            q.pop();
            i=j+1;
            j++;
            while(j<data.size()&&data[j]!=',')++j;
            string s=data.substr(i,j-i);
            if(s!="null"){
                cur->left=new TreeNode(stoi(s));
                q.push(cur->left);
            }
            i=j+1;
            j++;
            while(j<data.size()&&data[j]!=',')++j;
            s=data.substr(i,j-i);
            if(s!="null"){
                cur->right=new TreeNode(stoi(s));
                q.push(cur->right);
            }   
        }
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

Time complexity O(n)

Spatial complexity O(n)