一、从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

思路分析：
这里我们随便给一颗二叉树分析一下

我们遍历从前往后遍历先序数组，第一位就是二叉树的根节点，然后在中序遍历中找到该结点，该节点为分界线，该节点的左边的就是根节点的左子树，右边的就是右子树。

然后去构建根节点的左子树，遍历先序数组，然后在中序数组中找到该结点，左边的就是左子树，右边的就是右子树。

我们可以发现安装这个思路可以将二叉树构建出来，但是我们需要考虑一些条件，什么条件的时候，应该停止，首先中序遍历的数组的left应该小于right，还有得保证中序遍历中找到先序遍历的元素，否则返回-1下标，停止递归。

public int pre = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return sortTree(preorder,inorder,0,inorder.length - 1);
    }
    public TreeNode sortTree(int[] preorder,int[] inorder,int left,int right) {
        //1.判断是否还有左右子树
        if(left > right) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[pre]);
        int index = findIndex(inorder,left,right,preorder[pre]);
        if(index == -1) {
            return null;
        }
        pre++;
        root.left = sortTree(preorder,inorder,left,index - 1);
        root.right = sortTree(preorder,inorder,index + 1,right);
        return root;
    }
    public int findIndex(int[] inorder,int left,int right,int val) {
        if(left > right) {
            return  -1;
        }
        for (int i = left; i <= right; i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }

二、从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

思路分析：
这里我们随便给一颗二叉树分析一下

这次我们从后往前遍历后序数组，每遍历的一位都为该子树的根节点，不过我们得先遍历右子树，因为后序遍历的顺序是左子树-》右子树-》根节点，我们从后往前遍历后序数组，相当于反着来。中序遍历找到先序遍历的元素，左边的为左子树，右边的为右子树。

我们可以发现安装这个思路可以将二叉树构建出来，但是我们需要考虑一些条件，什么条件的时候，应该停止，首先中序遍历的数组的left应该小于right，还有得保证中序遍历中找到先序遍历的元素，否则返回-1下标，停止递归。
而且我们定义后序数组遍历下标时，因为我们是从后往前遍历，所以我们应定义为数组大小-1.

public int last = 0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        last = inorder.length - 1;
        return sortTree1(postorder,inorder,0,inorder.length - 1);
    }
    public TreeNode sortTree1(int[] postorder,int[] inorder,int left,int right) {
        //1.判断是否还有左右子树
        if(left > right) {
            return null;
        }
        //找到中序遍历位置
        TreeNode root = new TreeNode(postorder[last]);
        int index = findIndex1(inorder,left,right,postorder[last]);
        if(index == -1) {
            return null;
        }
        last--;
        //构建左右子树
        root.right = sortTree1(postorder,inorder,index + 1,right);
        root.left = sortTree1(postorder,inorder,left,index - 1);
        return root;
    }
    public int findIndex1(int[] inorder,int left,int right,int val) {
        if(left > right) {
            return  -1;
        }
        for (int i = left; i <= right; i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }

三、根据二叉树创建字符串

给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

思路分析：
按照题目的大意，就是先序二叉树，在有些情况下加入( 或者 ),我们来具体分析下什么情况下应该加什么。

我们可以发现，根节点不用加任何括号，在遍历其他任何结点时加一个 ( 返回该节点时加一个 ），但还有一些边界条件需要判断一下。我们发现当左子树为空时，右子树不为空时，得加一个完整的括号，不然会破坏一一映射关系。

还有一点就是我们不断地拼接字符串，所以我们使用StringBuilder对象去拼接，然后toString,不然会创建大量String对象浪费空间。

public String tree2str(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        treeToStr(root,sb);
        return sb.toString();
    }
    public void treeToStr(TreeNode root,StringBuilder sb) {
        if(root == null) {
            return;
        }
        sb.append(root.val);
        if(root.left != null) {
            sb.append("(");
            treeToStr(root.left,sb);
            sb.append(")");
        } else {
            if(root.right == null) {
                return;
            }else {
                sb.append("()");
            }
        }
        if(root.right == null) {
            return;
        } else {
            sb.append("(");
            treeToStr(root.right,sb);
            sb.append(")");
        }
    }