題目
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.

Example:
Input: "4(2(3)(1))(6(5))"
Output: return the tree root node representing the following tree:

       4
     /   \
    2     6
   / \   / 
  3   1 5   

Note:
There will only be '(', ')', '-' and '0' ~ '9' in the input string.
An empty tree is represented by "" instead of "()".

答案

class Solution {
    public TreeNode str2tree(String s) {
        if(s.equals("")) return null;
        TreeNode root = recur(s);
        return root;
    }

    public TreeNode recur(String s) {
        if(s.equals("")) return null;
        // First character is root's value
        TreeNode t;
        int first_left_paren = s.indexOf('('), counter = 0, left = first_left_paren, right = s.length() - 1;
        
        if(first_left_paren != -1) {
            t = new TreeNode(Integer.parseInt(s.substring(0, first_left_paren)));
            while(left <= right) {
                char c = s.charAt(left);
                if(c == '(') counter++;
                if(c == ')') counter--;
                if(counter == 0) break;
                left++;
            }
            t.left = recur(s.substring(first_left_paren + 1, left));
            if(left == right)
                t.right = null;
            else
                t.right = recur(s.substring(left + 2, right));
               
        }
        else {
            t = new TreeNode(Integer.parseInt(s));
        }
        return t;
    }
}