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.

1 2 3 4 5 6 7 8 9 |
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 “()”.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
/** * 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; } }; |

` `