# AC cpp recursive and iterative solution

• ``````TreeNode* str2treeHelper(string s, int& idx, int n) {
int start = idx;
int cnt = 0;
int neg = 1;
if (s[idx] == '-') {
idx++;
start++;
neg = -1;
}
while (idx < n && isdigit(s[idx])) {
idx++;
}
if (idx == start) {
return nullptr;
}
string val = s.substr(start, idx - start);
TreeNode* root = new TreeNode(stoi(val) * neg);
while (idx < n) {
if (s[idx] == '(') {
cnt++;
idx++;
if (cnt == 1) {
root->left = str2treeHelper(s, idx, n);
} else {
root->right = str2treeHelper(s, idx, n);
}
} else if (s[idx] == ')') {
idx++;
return root;
}
}

return root;
}

TreeNode* str2tree(string s) {
int n = s.size();
if (n < 1) {
return nullptr;
}

int idx = 0;

return str2treeHelper(s, idx, n);
}

``````
``````TreeNode* str2tree(string s) {
int n = s.size();
if (n < 1) {
return nullptr;
}

int i = 0;
stack<pair<TreeNode*, int>> stk;

while (i < n) {
if (s[i] == '-' || isdigit(s[i])) {
int neg = 1;
if (s[i] == '-') {
neg = -1;
i++;
}
int sum = 0;
while (i < n && isdigit(s[i])) {
sum = sum * 10 + s[i] - '0';
i++;
}
sum *= neg;
stk.push(make_pair(new TreeNode(sum), 0));
} else if (s[i] == ')') {
if (s[i - 1] == '(') {
stk.top().second++;
i++;
continue;
}
auto top = stk.top();
stk.pop();
auto& p = stk.top();
if (p.second == 0) {
p.first->left = top.first;
} else {
p.first->right = top.first;
}
p.second++;
i++;
} else {
i++;
}
}

return stk.top().first;
}
``````

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