# Leetcode 536. Construct Binary Tree from String

You need to construct a binary tree from a string consisting of parenthesis and integers.

The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root’s value and a pair of parenthesis contains a child binary tree with the same structure.

You always start to construct the left child node of the parent first if it exists.

```Example:
Input: "4(2(3)(1))(6(5))"
Output: return the tree root node representing the following tree:

4
/   \
2     6
/ \   /
3   1 5```

Note:
There will only be ‘(‘, ‘)’, ‘-‘ and ‘0’ ~ ‘9’ in the input string.
An empty tree is represented by “” instead of “()”.

```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* str2tree(string s) {
int i = 0;
return dfs(s, i);
}

int get_next_num(string &s, int &i) {
int start = i;
while (i != (int)s.size() && s[i] != '(' && s[i] != ')')
i++;

return stoi(s.substr(start, i - start));
}
/*
0123456789
4(2(3)(1))(6(5))

4(2)(3)

*/
TreeNode *dfs(string &s, int &i) {
//base case
int size = s.size();
if (i >= size || s[i] == ')')
return NULL;

if (s[i] == '(')
i++;

int num = get_next_num(s, i);
TreeNode *root = new TreeNode(num);

TreeNode *left = dfs(s, i);
TreeNode *right = dfs(s, i);

root->left = left;
root->right = right;

if (s[i] == ')')
i++;

return root;
}
};```

` `

# 像大佬一样

Nothing in this world can take the place of persistence. Talent will not; nothing is more common than unsuccessful men with talent. Genius will not; unrewarded genius is almost a proverb. Education will not; the world is full of educated derelicts. Persistence and determination alone are omnipotent. The slogan Press On! has solved and always will solve the problems of the human race