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

• 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);
}
};
``````

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