[lintcode] problem 880 – construct binary tree from string

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

There will only be ‘(‘, ‘)’, ‘-‘ and ‘0’ ~ ‘9’ in the input string.
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:

No.2

Input: “1(-1)”

Output: {1,-1}

Explanation:
The output is look like this:

1
2
3

   1
  /
-1

Code

public class  {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

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

[lintcode] problem 880 – construct binary tree from string

Note

Example

No.1

No.2

Code

近期文章

近期评论

标签

热门

文章归档

分类目录

功能