536. Construct Binary Tree from String

Problem:

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:

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

Analysis:

Partition string to get the correct string for subtree. The above example can be partition to root: 4, left: 2(3)(1), right 6(5). 

Solution:

 class Solution {  
   public TreeNode str2tree(String s) {  
           if (s == null || s.length() == 0)  
                return null;  
           int firstLeftParIndex = s.indexOf('(');  
           int val = firstLeftParIndex == -1 ? Integer.valueOf(s) : Integer.valueOf(s.substring(0, firstLeftParIndex));  
           TreeNode root = new TreeNode(val);  
           if (firstLeftParIndex == -1)  
                return root;  
           int count = 1, secondLeftIndex = 0;  
           for (int i = firstLeftParIndex + 1; i < s.length(); i++) {  
                char c = s.charAt(i);  
                if (c == '(') count++;  
                else if (c == ')') count--;  
                if (count == 0 && secondLeftIndex == 0) {  
                     root.left = str2tree(s.substring(firstLeftParIndex + 1, i));  
                     secondLeftIndex = i + 1;  
                }   
                else if (count == 0) {  
                     root.right = str2tree(s.substring(secondLeftIndex + 1, i));  
                }  
           }  
           return root;  
   }  
 }