括号字符串表示的二叉树，用栈转换为树结构_python 括号树转化为树

题目描述：字符串str="1(2(3,4(,5)),6(7,))"表示一棵二叉树，其中A（B，C）表示A为根结点，B和C为A的左右子节点。根据字符串输出二叉树的中序遍历。

思路：利用栈记录当前构建子树的根结点，利用方向标识记录当前构建子树方向（左子树/右子树）。具体步骤如下：

1. 遇到左括号，说明开始构建新的子树，将左括号之前的值入栈并且将方向flag置为true（表示接下来构建左子树）。此时栈顶记录的是当前构造子树的根结点；

2. 遇到右括号，说明当前子树构建完毕，将栈顶元素弹出，并且将方向flag置为false。因为当前子树构建完毕，接下来只能是构造右子树或者继续向上回溯（向上回溯后也是构造右子树，因此相同的处理），flag置为false；

3. 遇到逗号，说明左子树构建完成，接下来构建右子树，将方向flag置为false。

4. 遇到普通value，将value包装为结点，根据方向flag连接到栈顶元素的左子节点/右子节点。

    //结点数据结构
    class MiNode{
        char val;
        MiNode left=null,right=null;
 
        MiNode(char val){
            this.val=val;
        }
    }
    
    //树的中序遍历
    public StringBuffer midTrace(MiNode root){
        StringBuffer answer=new StringBuffer();
        if(root==null) return answer;
 
        answer.append(midTrace(root.left));
        answer.append(root.val);
        answer.append(midTrace(root.right));
 
        return answer;
    }
 
    //将字符串转换为树结构
    public String midTraceByStack(String str){
        String answer="";
        if(str==null||str.length()==0) return answer;
 
        char[] chars=str.toCharArray();
        Stack<MiNode> stack=new Stack<>();
        boolean dircFlag=true;
 
        //临时变量
        int length=chars.length;
        char currentValue=chars[0];
        MiNode node=new MiNode(currentValue);
        //保存根结点位置
        MiNode root=node;
 
        for(int i=1;i<length;i++){
            currentValue=chars[i];
            //当前字符的四种情况
            if(currentValue=='('){
                stack.push(node);
                dircFlag=true;
            }
            else if(currentValue==')'){
                stack.pop();    
                dircFlag=false;
            }
            else if(currentValue==','){
                dircFlag=false;
            }
            else{
                node=new MiNode(currentValue);
                if(dircFlag){
                    stack.peek().left=node;
                }
                else{
                    stack.peek().right=node;
                }
            }
        }
        //树的中序遍历
        answer=midTrace(root).toString();
        return answer;
    }