Leetcode 536. 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.

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 "()"

Code (Java):

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int start = 0;
    public TreeNode str2tree(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }

        return str2treeHelper(s);
    }

    private TreeNode str2treeHelper(String s) {
        if (start >= s.length()) {
            return null;
        }

        // parse int
        //
        boolean neg = false;
        if (s.charAt(start) == '-') {
            neg = true;
            start++;
        }
        int num = 0;
        while (start < s.length() && Character.isDigit(s.charAt(start))) {
            int digit = Character.getNumericValue(s.charAt(start));
            num = num * 10 + digit;
            start++;
        }

        if (neg) {
            num = -num;
        }

        TreeNode root = new TreeNode(num);

        if (start >= s.length()) {
            return root;
        }

        // go to left child
        //
        if (start < s.length() && s.charAt(start) == '(') {
            start++;
            root.left = str2treeHelper(s);
        }

        if (start < s.length() && s.charAt(start) == ')') {
            start++;
            return root;
        }

        // go to the right child
        //
        if (start < s.length() && s.charAt(start) == '(') {
            start++;
            root.right = str2treeHelper(s);
        }

        if (start < s.length() && s.charAt(start) == ')') {
            start++;
            return root;
        }

        return root;
    }
}