536. Construct Binary Tree from String (Medium)

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

Solution 1: Recursion 36ms

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    TreeNode* preorder(string& s, int& i) {
        if (i == s.size()) return NULL;
        int val = 0, sign = 1, n = s.size();
        if (s[i] == '-') { ++i; sign = -1; }
        while (i < n && s[i] >= '0' && s[i] <= '9') val = 10*val+s[i++]-'0';
        TreeNode* root = new TreeNode(val*sign);

        if (i < n && s[i] == '(') {
            root->left = preorder(s, ++i);
            ++i; // remove ')'
        }
        if (i < n && s[i] == '(') {
            root->right = preorder(s, ++i);
            ++i; // remove ')'
        }
        return root;
    }
public:
    TreeNode* str2tree(string s) {
        int i = 0;
        return preorder(s, i);
    }
};