536 Construct Binary Tree from String

536. Construct Binary Tree from String

1. Question

You need to construct a binary tree from a string consisting of parenthesis and integers.
The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root's value and a pair of parenthesis contains a child binary tree with the same structure.
You always start to construct theleftchild node of the parent first if it exists.
Example:
1
Input: "4(2(3)(1))(6(5))"
2
3
Output: return the tree root node representing the following tree:
4
5
4
6
/ \
7
2 6
8
/ \ /
9
3 1 5
Copied!
Note:
  1. 1.
    There will only be'(',')','-'and'0'~'9'in the input string.
  2. 2.
    An empty tree is represented by""instead of"()".

2. Implementation

(1) Recursion
1
class Solution {
2
int i;
3
public TreeNode str2tree(String s) {
4
i = 0;
5
return buildTree(s);
6
}
7
8
public TreeNode buildTree(String s) {
9
StringBuilder num = new StringBuilder();
10
11
while (i < s.length() && (s.charAt(i) == '-' || Character.isDigit(s.charAt(i)))) {
12
num.append(s.charAt(i));
13
i++;
14
}
15
16
if (num.length() == 0) {
17
return null;
18
}
19
20
TreeNode root = new TreeNode(Integer.parseInt(num.toString()));
21
22
// Left SubTree
23
if (i < s.length() && s.charAt(i) == '(') {
24
// Skip '('
25
++i;
26
root.left = buildTree(s);
27
// Skip ')'
28
++i;
29
}
30
31
// Right SubTree
32
if (i < s.length() && s.charAt(i) == '(') {
33
++i;
34
root.right = buildTree(s);
35
++i;
36
}
37
return root;
38
}
39
}
Copied!
(2) Iteration
1
class Solution {
2
public TreeNode str2tree(String s) {
3
if (s == null || s.length() == 0) {
4
return null;
5
}
6
7
Stack<TreeNode> stack = new Stack<>();
8
9
for (int end = 0, start = 0; end < s.length(); end++, start = end) {
10
char c = s.charAt(end);
11
12
if (c == '(') {
13
continue;
14
}
15
else if (c == ')') {
16
stack.pop();
17
}
18
else {
19
while (end + 1< s.length() && Character.isDigit(s.charAt(end + 1))) {
20
++end;
21
}
22
TreeNode curNode = new TreeNode(Integer.parseInt(s.substring(start, end + 1)));
23
24
if (!stack.isEmpty()) {
25
TreeNode parentNode = stack.peek();
26
if (parentNode.left != null) {
27
parentNode.right = curNode;
28
}
29
else {
30
parentNode.left = curNode;
31
}
32
}
33
stack.push(curNode);
34
}
35
}
36
return stack.isEmpty() ? null : stack.peek();
37
}
38
}
Copied!

3. Time & Space Complexity

Recursion: 时间复杂度O(n), 空间复杂度O(n)
Iteration: 时间复杂度O(n), 空间复杂度O(n)