536. Construct Binary Tree from

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

Solution1：Recursive

思路：
首先我们要做的是先找出根结点值，我们找第一个左括号的位置，如果找不到，说明当前字符串都是数字，直接转化为整型，然后新建结点返回即可。
否则的话从当前位置开始遍历，因为当前位置是一个左括号，我们的目标是找到与之对应的右括号的位置，但是由于中间还会遇到左右括号，所以我们需要用一个变量cnt来记录左括号的个数，如果遇到左括号，cnt自增1，如果遇到右括号，cnt自减1，这样当某个时刻cnt为0的时候，我们就确定了一个完整的子树的位置。那么问题来了，这个子树到底是左子树还是右子树呢，我们需要一个辅助变量start，当最开始找到第一个左括号的位置时，将start赋值为该位置，那么当cnt为0时，如果start还是原来的位置，说明这个是左子树，我们对其调用递归函数，注意此时更新start的位置，这样就能区分左右子树了
Time Complexity: O(N) Space Complexity: O(N)

Solution2：Stack

思路：
借助栈stack来实现。
遍历字符串s，用变量j记录当前位置i，
如果遇到的是左括号，什么也不做继续遍历；
如果遇到的是数字或者负号，那么我们将连续的数字都找出来，然后转为整型并新建结点，
此时我们看stack中是否有结点，如果有的话，当前结点就是栈顶结点的子结点，如果栈顶结点没有左子结点，那么此结点就是其左子结点，反之则为其右子结点。之后要将此结点压入栈中。
如果我们遍历到的是右括号，说明栈顶元素的子结点已经处理完了，将其移除栈。

Time Complexity: O(N) Space Complexity: O(N)

Solution1 Code：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
// Input: "4(2(3)(1))(6(5))"

class Solution {
    public TreeNode str2tree(String s) {
        if (s == null || s.length() == 0) return null;
        int firstParen = s.indexOf("(");
        int val = firstParen == -1 ? Integer.parseInt(s) : Integer.parseInt(s.substring(0, firstParen));
        TreeNode cur = new TreeNode(val);
        if (firstParen == -1) return cur;
        
        int start = firstParen, leftParenCount = 0;
        
        for (int i=start;i<s.length();i++) {
            if (s.charAt(i) == '(') leftParenCount++;
            else if (s.charAt(i) == ')') leftParenCount--;
            
            // left ()
            if (leftParenCount == 0 && start == firstParen) {
                cur.left = str2tree(s.substring(start+1,i)); 
                start = i+1; //从left()的) 跳到 right()的(
            }
            // right ()
            else if (leftParenCount == 0) {
                cur.right = str2tree(s.substring(start+1,i));
            }
        }
        return cur;
    }
}

Solution2 Code：

// Input: "4(2(3)(1))(6(5))"

public class Solution {
    public TreeNode str2tree(String s) {
        Stack<TreeNode> stack = new Stack<>();
        for(int i = 0, j = i; i < s.length(); i++, j = i){
            char c = s.charAt(i);
            if(c == ')')    stack.pop();
            else if(c >= '0' && c <= '9' || c == '-'){
                while(i + 1 < s.length() && s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9') i++;
                TreeNode currentNode = new TreeNode(Integer.valueOf(s.substring(j, i + 1)));
                if(!stack.isEmpty()){
                    TreeNode parent = stack.peek();
                    if(parent.left != null)    parent.right = currentNode;
                    else parent.left = currentNode;
                }
                stack.push(currentNode);
            }
        }
        return stack.isEmpty() ? null : stack.peek();
    }
}