Shared my C++ BFS solution ,base on c_type_str and int *


  • 0

    This idea is come up with by my roommate @HelloKenLee, and beat 92%

    Example

    Maybe I can post a example firstly,Consider the following example.

           1
         /   \
        2   nullptr
       / \ 
      3   4
    

    After encoding ,we get the data string (For more readable ,I would use Decimal instead of Binaryand add '.' between two num which represent 1 TreeNode **)

    string encoding = "1.1     1.2     0    1.3     1.4     0     0"
                       /\/\            /\
                       |                |
                   (flag)(num)   (just flag It's nullptr node)
    

    How to serialize the tree

    This idea is similar to representation of INT,we use a sign bit,and data bits.

    1. So,we can use 1 int to represent this data whether is NULL or TreeNode,if it's a TreeNode we use one more bit to represent its num(int).
    2. We can stored each TreeNode base on level traversal,and we can use string constructor(const *char ptr,u_size n) to conver int to string like this encode += string(reinterpret_cast<char*>(&flag),4);
    3. I have no idea to use 1 bit to represent the "flag" bit due to principle of 4 byte alignment.If you figure out this,please let me know!

    How to deserialize the data

    It's not difficult to deserialize the data while you serialize the tree successfully :),But firstly , maybe you should use cast to conver string to char *,like this

    char *str = const_cast<char*>(data.c_str());
    int* pointer = reinterpret_cast<int*> (str);
    

    Behind this cast is a simple BFS operation

    Detailed implementation you can see the following code

    Detailed implementation but not concise

    class Codec {
    public:
    
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            queue<TreeNode*> que;
            string encode;
            int flag;
            if(!root)
                que.push(nullptr);
            else
                que.push(root);
            while(!que.empty()){
                TreeNode *tmp = que.front();
                que.pop();
                if(tmp==nullptr){
                    flag = 0;
                    encode += string(reinterpret_cast<char*>(&flag),4);
                    //cout<<string(reinterpret_cast<char*>(&flag),4)<<endl;
                }
                else{
                    flag = 1;
                    int num = tmp->val;
                    encode += string(reinterpret_cast<char*>(&flag),4) + string(reinterpret_cast<char*>(&num),4);
                    que.push(tmp->left);
                    que.push(tmp->right);
                    //cout<<string(reinterpret_cast<char*>(&flag),4) + string(reinterpret_cast<char*>(&num),4)<<endl;
                }
            }
            return encode;
            
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            char *str = const_cast<char*>(data.c_str());
            int* pointer = reinterpret_cast<int*> (str);
            //TreeNode *dummy = new TreeNode();
            
            if(*pointer==0){///root为空
                return nullptr;
            }
            ++pointer;
            TreeNode *root = new TreeNode(*pointer);
            queue<TreeNode*> que;
            que.push(root);
            ++pointer;
            while(!que.empty()){
                TreeNode *tmp = que.front();
                que.pop();
                if(tmp==nullptr){
                    continue;
                }
                if(*pointer++ == 0){
                    tmp->left == nullptr;
                }
                else{
                    tmp->left = new TreeNode(*pointer++);                
                    que.push(tmp->left);
                }///左子树
                if(*pointer++ == 0){
                    tmp->right == nullptr;
                }
                else{
                    tmp->right = new TreeNode(*pointer++);
                    que.push(tmp->right);
                }
            }
            return root;
        }
    
    };
    

    Concise solution

    class Codec {
    public:
    
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            queue<TreeNode*> que;
            string encode;
            int flag;
            que.push(root);
            while(!que.empty()){
                TreeNode *tmp = que.front();
                que.pop();
                flag = tmp == nullptr ? 0 : 1;
                encode += string(reinterpret_cast<char*>(&flag),4);
                if(flag){
                    int num = tmp->val;
                    encode += string(reinterpret_cast<char*>(&num),4);
                    que.push(tmp->left);
                    que.push(tmp->right);
                }
            }
            return encode;
            
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            char *str = const_cast<char*>(data.c_str());
            int* pointer = reinterpret_cast<int*> (str);
      
            if(*pointer++==0){//root == nullptr
                return nullptr;
            }
            TreeNode *root = new TreeNode(*pointer++);
            queue<TreeNode*> que;
            que.push(root);
            while(!que.empty()){
                TreeNode *tmp = que.front();
                que.pop();
                if(tmp == nullptr)
                    continue;
                    
                if(tmp->left = *pointer++ == 0 ? nullptr : new TreeNode(*pointer++))//left subtree
                    que.push(tmp->left);
                
                if(tmp->right = *pointer++ == 0 ? nullptr : new TreeNode(*pointer++))//right subtree
                    que.push(tmp->right);
            }
            return root;
        }
    
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.