由()和数字组成的字符串，数字代表二叉树结点的值，数字旁边的括号括起来的表示一颗完整的（子）树，把字符串还原成二叉树。类似eval expression，括号内的是递归子问题，用global pos记录当前处理到的位置，每个递归内再额外用lbc记录遇到的左括号的数目来区分当前返回的子结果是左子树还是右子树。
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param s: a string
* @return: a root of this tree
*/
int pos = 0;
TreeNode * str2tree(string &s) {
TreeNode *cur = nullptr;
int num = 0, sign = 1, lbc = 0;
while (pos < s.size()) {
const auto c = s[pos++];
if (c == '-') {
sign = -1;
} else if (c >= '0' && c <= '9') {
num = num * 10 + (c - '0');
} else if (c == '(') {
if (cur == nullptr) cur = new TreeNode(sign * num);
++lbc;
if (lbc == 1) cur->left = str2tree(s);
else cur->right = str2tree(s);
} else {
if (lbc == 0) {
cur = new TreeNode(sign * num);
}
break;
}
}
return cur;
}
};