[LeetCode] 536. Construct Binary Tree from String

https://leetcode.com/contest/leetcode-weekly-contest-23/problems/construct-binary-tree-from-string/

Solution:
The basic idea is to form the root first; then form the left children; then the right one. So we will use recursion strategy. See code below:

Note: The description for this question is not very clear, for example: the meaning of the '-' (it means negative number actually), and also the number can be larger than 10...

Code:

/**
 * 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) {
        TreeNode* res;
        int n = s.size(), i = 0;
        if(n==0) return NULL;
        int flag = 1;
        if(s[i] == '-'){
            flag = -1;
            ++i;
        }
        if(i<n&&(s[i]-'0'>=0)&&(s[i]-'0'<=9)) {
            int t=0; 
            while(i<n&&(s[i]-'0'>=0)&&(s[i]-'0'<=9)) t = t*10 + (s[i++]-'0');
            res = new TreeNode(flag*t); 
        }
        if(i<n&&s[i]=='('){
            int t = 1, ct = i+1;
            while(t>0&&ct<n){
                if(s[ct]=='(') ++t;
                if(s[ct]==')') --t;
                ++ct;
            } 
            if(t==0)res->left = str2tree(s.substr(i+1, ct-i-1)); //left children;
            if(t==0&&ct<n&&s[ct]=='(')res->right = str2tree(s.substr(ct+1, n-ct-2));//right children;
        }
        return res;
    }
};