O(n) 26 ms solution in format "1(2(,3),4(5,6(7,8)))"


  • 0
    U

    In this format, we can take ',' as the ending point of the left subtree, and ')' as the ending point of the right subtree.
    This compact form cound save some space when the tree is big.

    class Codec {
    private:
        TreeNode* decode(const string& data){        
            const char* s = data.c_str();
            int k = 0, i = 0, n = data.size(), v = 0;
            bool neg = false;
            
            TreeNode* p;
            stack<TreeNode*> st;
            for(; i <= n; ++i){//stop after '\0', so that the last ')' is dealt with properly
                char c = s[i];
                if(c == '-'){
                    neg = true;
                    continue;
                }
                if(isdigit(c)){
                    v = v * 10 + c - '0';
                    continue;
                }
    
                if(s[i-1] != ')'){
                    if(neg) v = -v;
                    //v = strtoi(data[k:i]) now, which is the subtree root' value
                    if(k == i) p = NULL;
                    else p = new TreeNode(v);
                    st.push(p);
                }
    
                switch(c){
                    case ',':
                        p = st.top();
                        st.pop();
                        st.top()->left = p;
                        break;
                    case ')':
                        p = st.top();
                        st.pop();
                        st.top()->right = p;
                        break;
                }
                
                k = i+1;
                v = 0;
                neg = false;
            }
            
            return st.top();
        }
        
        string encode(TreeNode* root){
            string s = to_string(root->val);
            
            if(root->left == NULL && root->right == NULL){
                return s;
            }
            
            s += '(';
            if(root->left) s += encode(root->left);
            s += ',';
            if(root->right) s += encode(root->right);
            s += ')';
            
            return s;
        }
        
    public:
    
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            if(root == NULL) return "";
            return encode(root);
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            if(data.empty()) return NULL;
            return decode(data);
        }
    };
    

Log in to reply
 

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