/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode str2tree(String s) {
// Base case
if (s.length() == 0) return null;
// Create root
int i = 0, j = 0;
while (j < s.length() && (Character.isDigit(s.charAt(j)) || s.charAt(j) == '-')) j++;
TreeNode root = new TreeNode(Integer.valueOf(s.substring(i, j)));
// Left child
if (j < s.length()) {
i = j;
int count = 1;
while (j + 1 < s.length() && count != 0) {
j++;
if (s.charAt(j) == ')') count--;
if (s.charAt(j) == '(') count++;
}
root.left = str2tree(s.substring(i + 1, j));
}
j++;
// Right child
if (j < s.length()) {
root.right = str2tree(s.substring(j + 1, s.length() - 1));
}
return root;
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
int index;
public TreeNode str2tree(String s) {
if(s.length() == 0) return null;
char[] c = s.toCharArray();
index = 0;
return helper(c);
}
public TreeNode helper(char[] c){
if(index >= c.length) return null;
int num = 0;
boolean sign = true;
if(c[index] == '-')
{
sign = false;
index++;
}
while( index < c.length && c[index] >= '0' && c[index] <= '9') {
num = num * 10 + c[index] - '0';
index++;
}
if(!sign) num = -num;
TreeNode res = new TreeNode(num);
if(index < c.length && c[index] == '('){
index++;
res.left = helper(c);
}
if(index < c.length && c[index] == '('){
index++;
res.right = helper(c);
}
if(index < c.length && c[index] == ')')
index++;
return res;
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode str2tree(String s) {
if(s.length()==0) return null;
char[] c = s.toCharArray();
int index = 0;
int sign = 1;
if(c[index]=='-') {sign=-1; index++;}
int num = 0;
while(index<c.length && c[index]>='0' && c[index]<='9'){
num = num * 10 + c[index]-'0';
index++;
}
num = num*sign; sign = 1;
TreeNode root = new TreeNode(num);
Stack<TreeNode> st = new Stack();
st.push(root);
while(index<c.length)
{
if(c[index]=='(')
{
index++;
if(c[index]=='-') {sign=-1; index++;}
num = 0;
while(index<c.length && c[index]>='0' && c[index]<='9'){
num = num * 10 + c[index]-'0';
index++;
}
num = num*sign; sign = 1;
TreeNode r = st.peek();
TreeNode child = new TreeNode(num);
if(r.left==null) r.left = child;
else r.right = child;
st.push(child);
}
if(c[index]==')') {st.pop(); index++;}
}
return root;
}
}