My C++ solutions (recursive and non-recursive), O(N) time and space, encode each node as val+" " + nodeType + " "


  • 0
    D

    The idea is to do pre-order travesal and encode each visited node as val + " " + nodeType.
    nodeType is defined as 0: no child node, 1: only has left child, 2: only has right child, 3: has both children
    Encoder/decoder can be implemented in a recusive way.,

    class Codec {
    private:
        TreeNode *helper(istringstream &iS)
        {
             int val, nodeType;
             iS>>val>>nodeType;
             TreeNode *root;  
             root = new TreeNode(val); // recover the current node
             if(nodeType & 0x1) root->left  = helper(iS); // recover the left subtree
             if(nodeType & 0x2) root->right = helper(iS); // recover the right subtree
             return root;
        }
        
    public:
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            string res;
            int nodeType = 0;
            if(!root) return res; // if it is an empty tree, just return an empty string
            res += to_string(root->val) + " "; // otherwise, encode root and root->val + " " + nodetype+ " "
            if(root->left) nodeType +=1;
            if(root->right) nodeType +=2;
            res += to_string(nodeType) + " ";
            
           // recursively encode the left subtree and right subtree
            res += serialize(root->left);
            res += serialize(root->right);
            return res;
        }
    
        TreeNode* deserialize(string data) {
             if(data.size()==0) return nullptr;
             istringstream iS(data);
             return helper(iS);
        }
    };
    

    Another non-recusive method, queue based breadth-first travesal. same node encoding scheme

    class Codec {
    public:
    
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            queue<TreeNode *> nodeQ;
            string res;
            int nodeType;
            if(root) nodeQ.push(root);
            while(!nodeQ.empty())
            {
                root = nodeQ.front();
                nodeQ.pop();
                nodeType = 0;
                if(root->left) 
                {
                    nodeType +=1;
                    nodeQ.push(root->left);
                }
                if(root->right) 
                {
                    nodeType +=2;
                    nodeQ.push(root->right);
                }
                res += to_string(root->val) + " " + to_string(nodeType) + " ";
            }
            return res;
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            if(data.size()==0) return nullptr;
            istringstream iS(data);
            int  nodeType;
            TreeNode *root = new TreeNode(0), *cur;
            queue<TreeNode *> nodeQ;
            nodeQ.push(root);
            while(!nodeQ.empty())
            {
                cur = nodeQ.front();
                nodeQ.pop();
                iS>>cur->val>>nodeType;
                if(nodeType & 0x1) nodeQ.push(cur->left = new TreeNode(0));
                if(nodeType & 0x2) nodeQ.push(cur->right = new TreeNode(0));
            }
            return root;
        }
    };

Log in to reply
 

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