TreeNode* str2tree(string s) {
        int i = 0;
        return s.empty() ? nullptr : create_tree(s, i);
    }

    TreeNode* create_tree(string s, int &i) {
        TreeNode* root;
        //cout << s.substr(i) << endl;

        int number = 0;
        int negitive = 1;
        if (s[i] == '-'){
            negitive = -1;
            i++;
        }

        while (s[i] >= '0' && s[i] <= '9') {
            number = number * 10 + s[i] - '0';
            i++;
        }

        root = new TreeNode(number*negitive);

        if (s[i] == '('){
            i++; // (
            root->left = create_tree(s, i);
            i++; // )
        }

        if (s[i] == '(') {
            i++; // (
            root->right = create_tree(s, i);
            i++; // )
        }

        return root;
    }
};