Construct Binary Tree from String

题目地址：
https://leetcode.com/problems/construct-binary-tree-from-string/description/

题目：

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

解题思路：
这道题就是用stack来解决。

代码：

public TreeNode str2tree(String s) {
    if(s == null || s.length() == 0){
        return null;
    }
    Stack<TreeNode> stack = new Stack<>();
    for(int i = 0; i <= s.length() - 1; i++){
        char c = s.charAt(i);
        if(c == ')'){
            TreeNode child = stack.pop();
            TreeNode parent = stack.pop();
            if(parent.left == null){
                parent.left = child;
            }
            else{
                parent.right = child;
            }
            stack.push(parent);
        }
        else if(c == '('){
            continue;
        }
        else{
            int sign = 1;
            int j = i;
            if(s.charAt(i) == '-'){
                sign = -1;
                j = i + 1;
            }
            while(j <= s.length() - 1 && Character.isDigit(s.charAt(j))){
                j++;
            }
            int val = Integer.parseInt(s.substring(i, j)) * sign;
            val *= sign;
            TreeNode curr = new TreeNode(val);
            stack.push(curr);
            i = j - 1;
        }
    }
    return stack.size() == 0 ? null : stack.pop();
}