Java根据二叉树的先序和后序得到二叉树

一般情况下，我们会根据先序和后序写出二叉树，但是用代码怎末写呢？

例如：

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

思路：我们先根据先序遍历找到根节点记录下来，在从中序数组中找到刚才记录下来根节点的下标，那么下标的左边就是根节点的左子树，后边就是根的右子树，依次递归求二叉树，递归截止条件在下图中说明：

开始状态

描述：

第一步，rootindex是根节点，begin和end是根节点的左右子树在中序数组的下标范围，下一步你们就明白了

第二步，我们找左子树，end=rootindex-1;begin不动

第三步，我们找右子树，end不动，begin=rootindex+1;

依次递归，每次都是先找根节点，再找左子树，后右子树，结束条件见就是begin>end的时候，解释：（相当于该节点是叶子节点）

代码展示：

  public  int preindex;//记录先序遍历的下标，如果放在递归的方法中递归后值发生改变
    public TreeNode buildTree(int[] preorder, int[] inorder) {
       return creatTree(0,inorder.length-1, preorder, inorder);
    }
    public TreeNode creatTree(int begin,int end,int [] preorder,int[] inorder){
        if (begin>end)return null;
        TreeNode root =new TreeNode(preorder[preindex]);
        int rootindex=find(begin, end, preorder[preindex], inorder);//获取根节点在中序数组中下标
        preindex++;
        root.left=creatTree( begin, rootindex-1, preorder, inorder);
        root.right=creatTree( rootindex+1, end, preorder, inorder);
        return root;
    }
    public int find(int begin,int end,int key,int[] inorder){
        for (int i = begin; i <=end ; i++) {
            if (inorder[i]==key)return i;
        }
        return -1;
    }