# 0536. Construct Binary Tree from String
###### tags: `Leetcode` `Facebook` `Medium`
## 思路
递归或者stack
## Code

class Solution {
    public TreeNode str2tree(String s) {
        Stack<TreeNode> stack = new Stack<>();
        int idx = 0;
        TreeNode head = new TreeNode();
        if(s.length()==0) return null;
        while(idx != s.length()){
            int num = 0;
            boolean negative = false;
            if(s.charAt(idx)=='-'){
                negative = true;
                idx++;
            }
            while(idx!=s.length() && s.charAt(idx)!='(' && s.charAt(idx)!=')'){
                num = num*10+s.charAt(idx)-'0';
                idx++;
            }
            num = negative?-num:num;
            
            TreeNode node = new TreeNode(num);
            if(!stack.isEmpty()){
                TreeNode prevNode = stack.pop();
                if(prevNode.left==null) prevNode.left = node;
                else prevNode.right = node;
                stack.push(prevNode);
            }
            else{
                head = node;
            }
            stack.push(node);
            
            while(idx!=s.length() && s.charAt(idx)==')'){
                stack.pop();
                idx++;
            }
            while(idx!=s.length() && s.charAt(idx)=='('){
                idx++;
            }
        }
        return head;
    }
}