BiruLyu
7/10/2017 - 8:14 PM

## 536. Construct Binary Tree from String(Stack).java

``````/**
* 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;
}

}``````