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):

?

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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

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