# Java Recursive Solution

• ``````public TreeNode str2tree(String s) {
if (s == null || s.length() == 0) return null;
int firstParen = s.indexOf("(");
int val = firstParen == -1 ? Integer.parseInt(s) : Integer.parseInt(s.substring(0, firstParen));
TreeNode cur = new TreeNode(val);
if (firstParen == -1) return cur;
int start = firstParen, leftParenCount = 0;
for (int i=start;i<s.length();i++) {
if (s.charAt(i) == '(') leftParenCount++;
else if (s.charAt(i) == ')') leftParenCount--;
if (leftParenCount == 0 && start == firstParen) {cur.left = str2tree(s.substring(start+1,i)); start = i+1;}
else if (leftParenCount == 0) cur.right = str2tree(s.substring(start+1,i));
}
return cur;
}
``````

• Your idea is so clear and brilliant!!!

• That's what I want, It's awesome!

• Awesome. Very clear and easy to understand. Thank you for sharing.

• Share my solution using recursion:
For example, we have string `4(2(3)(1))(6(5))`, to construct a binary tree, we can split the string to 3 parts:
`4`
`(2(3)(1))`
`(6(5))`

`4` is the root val;
`(2(3)(1))` is left tree;
`(6(5))` is right tree;

So the main part of code is how to split the string to 3 substrings:

``````    public TreeNode str2tree(String s) {
if(s.length() == 0) return null;
if(s.startsWith("(")){
s = s.substring(1, s.length() - 1);
}
char[] sc = s.toCharArray();
String[] strs = new String[3];
int count = 0, start = 0;
for(int i = 0; i < sc.length; i++){
if(sc[i] == '('){
if(count == 0){
for(int j = 0; j < 3; j++){
if(strs[j] == null) {
strs[j] = s.substring(start,i);
start = i;
break;
}
}
}
count++;
}
if(sc[i] == ')') count--;
}

for(int j = 0; j < 3; j++){
if(strs[j] == null) {
strs[j] = s.substring(start,s.length());
break;
}
}

TreeNode root = new TreeNode(Integer.parseInt(strs[0]));
if(strs[1] != null) root.left = str2tree(strs[1]);
if(strs[2] != null) root.right = str2tree(strs[2]);
return root;
}``````

• This is my recursion, beat 97%, just scan the string from left to right, every time we meet '(' , create left child node, then if we meet '(' again from the same parent node, we create right child node.

``````public class Solution {

int i = 0;

public TreeNode str2tree(String s)
{
if (s == null || s.length() == 0) { return null; }
return helper(s.toCharArray());
}

private TreeNode helper(char[] s)
{
// done
if (i == s.length) { return null; }

// extract number
StringBuilder num = new StringBuilder();
while (i < s.length && s[i] != '(' && s[i] != ')') { num.append(s[i]); i++; }

// create new node
TreeNode n = null;
if (num.length() != 0)
{
n = new TreeNode(Integer.parseInt(num.toString()));
}
// check parenthesis type
if (i < s.length && s[i] == '(')
{
// create left child node
i++;
n.left = helper(s);
i++;

if (i < s.length && s[i] == '(')
{
// create right child node
i++;
n.right = helper(s);
i++;
}
}
return n;
}
}
``````

• Use the queue in the recursion to avoid using the global item and no need to count the left and right parents.

``````    public TreeNode str2tree(String s) {
if(s.length()==0) return null;
for(int i=0;i<s.length();i++)
{
queue.offer(s.charAt(i));
}
return buildTree(queue);
}

public TreeNode buildTree(Queue<Character> queue) {
if(queue.isEmpty()) return null;
TreeNode node=new TreeNode(0);

int value=0;
int sign=1;
while(!queue.isEmpty())
{
char top = queue.poll();
if(top=='(')
{
if(node.left==null) node.left=buildTree(queue);
else node.right=buildTree(queue);
}
else if(top==')')
{
break;
}
else
{
if(top=='-')
{
sign=-1;
continue;
}
value=value*10+(top-'0');
}
}

node.val=sign*value;
return node;
}
``````

• @dongll very nice coding, I make it a bit more simpler:

``````private int index = 0;
public TreeNode str2tree(String st) {
if (index == st.length()) return null;
StringBuilder num = new StringBuilder(); //extract number
while (index < st.length()) {
char c = st.charAt(index);
if(c!='('&&c!=')') {
num.append(c);
index++;
} else break;
}
TreeNode node = new TreeNode(Integer.parseInt(num.toString())); // create new node
if (index < st.length() && st.charAt(index) == '('){// check parenthesis type
index++;
node.left = str2tree(st);// create left child node
index++;
if (index < st.length() && st.charAt(index) == '('){
index++;
node.right = str2tree(st);// create right child node
index++;
}
}
}``````

• Once you get leftParenCount==0, you can break.

• This post is deleted!

• I am afraid this solution is not O(n) but at least O(nlgn) and at most O(n^2), while @dongll @tongzhou2 's solution is O(n);

• The string has 3 parts : root (left)(right). However, (left) and (right) might be empty.
Actually, after we find the left part, we can break the loop and build right child using the rest string directly if the rest is not empty.
Here is my version. More concise.

``````class Solution {
public TreeNode str2tree(String s) {
if (s == null || s.length() == 0) {
return null;
}
int firstLeft = s.indexOf('(');
if (firstLeft == -1) {
return new TreeNode(Integer.parseInt(s));
}
TreeNode root = new TreeNode(Integer.parseInt(s.substring(0, firstLeft)));
int count = 0, i = firstLeft;
while (i < s.length()) {
if (s.charAt(i) == '(') {
count++;
} else if (s.charAt(i) == ')') {
count--;
}
if (count == 0) {
root.left = str2tree(s.substring(firstLeft + 1, i));
break;
}
i++;
}
if (i != s.length() - 1) {
root.right = str2tree(s.substring(i + 2, s.length() - 1));
}
return root;
}
}
``````

• This solution is O(n^2) time.

• public TreeNode str2tree(String s) {

``````    if(s.startsWith("(")){
s = s.substring(1, s.length()-1);
}

if(s == null || s.length() == 0){
return null;
}
int index = s.indexOf("(");
if(index == -1){
return new TreeNode(Integer.valueOf(s));
}
int num = 0;
int j = 0;
for(int i = index; i < s.length(); i++){
if(s.charAt(i) == '(') num++;
if(s.charAt(i) == ')') num--;
if(num == 0){
j = i;
break;
}
}

}``````

• Similar idea.

``````class Solution {
int pos=-1;
public TreeNode str2tree(String s) {
pos++; // remove the "("
if (pos>=s.length()) return null;
// get the number
int start=pos;
while (pos<s.length()){
if (s.charAt(pos)=='(' || s.charAt(pos)==')') break;
pos++;
}

TreeNode root=new TreeNode(Integer.parseInt(s.substring(start, pos)));
if (pos<s.length() && s.charAt(pos)=='('){
root.left=str2tree(s);
if (pos<s.length() && s.charAt(pos)=='(')
root.right=str2tree(s);
}
pos++; // remove ")"
return root;
}
}

``````

• @dongll like this solution than mostly voted, easy and clean.

• Adapt it to Python version

``````class Solution(object):
def str2tree(self, s):
"""
:type s: str
:rtype: TreeNode
"""
if not s:
return None

first_paren = s.find('(')
val = int(s) if first_paren == -1 else int(s[:first_paren])
cur = TreeNode(val)
if first_paren == -1:
return cur
start, counter = first_paren, 0
for i in xrange(start, len(s)):
if s[i] == '(':
counter += 1
elif s[i] == ')':
counter -= 1
if counter == 0 and start == first_paren:
cur.left = self.str2tree(s[start+1:i])
start = i + 1
elif counter == 0:
cur.right = self.str2tree(s[start+1:i])
return cur
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.