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; } };