C++ Accepted recursive solution


  • 0
    C
    // Binary tree is a recursive structure, so recursion is an easy way to do this
    // just use a symbol (here #) as the delimiter to wrap around a tree
    // also note that empty tree is ##
    // note no error checking done here for brevity
    class Codec {
    public:
        
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            if (root == NULL) {
                return "##";
            }
            string retval("#");
            
            retval += std::to_string(root->val);
            retval += serialize(root->left);
            retval += serialize(root->right);
            
            retval += "#";
            return retval;
        }
        
        TreeNode* deserialize_(string& data, int& pos) {
            if (data[pos] == '#' && data[pos+1] == '#') {
                pos += 2;
                return NULL;
            }
            
            pos++; //match open '#'
            
            size_t limiter = data.find_first_of('#', pos);
            string value = data.substr(pos, limiter-pos+1);
            int val = std::stoi(value);
            TreeNode* retval = new TreeNode(val);
            
            pos = limiter;
            
            TreeNode* left = deserialize_(data, pos);
            TreeNode* right = deserialize_(data, pos);
            retval->left = left;
            retval->right = right;
            
            pos++; //match close '#'
            return retval;
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            int pos=0;
            return deserialize_(data, pos);
        }
    };

Log in to reply
 

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