Verbose Java Solution, Recursion

• ``````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.parseInt(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;
}
}
``````

• while (j < s.length() && (Character.isDigit(s.charAt(j)) || s.charAt(j) == '-')) j++;

Thank you for the solution! I don`t understand above step. Why we need to check if s.charAt(j)=='-' ? Could you explain it?

• @bigoffer4all There are negative integers. i.e. "1(-1)(2)".

• It is difficult to get good performance using recursion. For C++, the run time could be up to O(n^2). I don't know Java though.

• ``````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;
}
}
``````

• Nice solution. May I know what's the time complexity for this code?

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