[LintCode] Problem 880 - Construct Binary Tree from String

Posted on | In ,

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 the left child node of the parent first if it exists.

Note

  1. There will only be ‘(‘, ‘)’, ‘-‘ and ‘0’ ~ ‘9’ in the input string.
  2. An empty tree is represented by “” instead of “()”.

Example

No.1

Input: “-4(2(3)(1))(6(5))”

Output: {-4,2,6,3,1,5}

Explanation:
The output is look like this:

1
2
3
4
5
    -4
   /  \
  2    6
 / \   / 
3   1 5

No.2

Input: “1(-1)”

Output: {1,-1}

Explanation:
The output is look like this:

1
2
3
   1
  /
-1

Code

1
2
3
4
5
6
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public TreeNode str2tree(String s) {
    if (s.length() <= 0)
        return null;

    int idx = s.indexOf("(");

    if (idx == -1)
        return new TreeNode(Integer.valueOf(s));

    int val = Integer.parseInt(s.substring(0, idx));
    TreeNode root = new TreeNode(val);
    int count = 0;
    int openIdx = idx;

    for (int i = idx; i < s.length(); i++) {
        if (s.charAt(i) == '(')
            count++;
        else if (s.charAt(i) == ')')
            count--;

        if (count == 0 && openIdx == idx) {
            root.left = str2tree(s.substring(idx + 1, i));
            openIdx = i + 1;
        } else if (count == 0)
            root.right = str2tree(s.substring(openIdx + 1, i));
    }

    return root;
}