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

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

思路：递归法。

第一步：确定参数与返回值。参数为中序数组，数组起始下标，终止下标，后序数组，数组起始下标，终止下标，返回值为树

第二步：确定终止条件。中序数组起始下标>=终止下标时说明划分完毕

第三步：确定单层递归逻辑。

1.如果数组大小为0，说明为空节点

2.如果数组大小不为0，后序遍历数组的最后一个元素是树的根节点

3.找到后序遍历数组的最后一个元素在中序遍历数组中的位置，作为切割点

4.切割中序数组，切割点前的值构成左子树，切割点后的值构成右子树

5.切割后序数组，切成后序左数组，后序右数组

6.递归处理左数组与右数组

代码：

   Map<Integer,Integer> map=new HashMap<>();//方便根据数值找数组下标
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        //构造中序数组的map
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        return findNode(inorder,0,inorder.length,postorder,0,postorder.length);
    }
    public TreeNode findNode(int[] inorder,int inBegin,int inEnd,int[] postorder,int postBegin,int postEnd){
        //分割的数组是前闭后开
        //1.如果数组大小为0，说明为空节点
        if(inBegin>=inEnd||postBegin>=postEnd) return null;

        //2.如果数组大小不为0，后序遍历数组的最后一个元素是树的根节点
        int rootValue=postorder[postEnd-1];
        TreeNode root=new TreeNode(rootValue);

        //3.找到后序遍历数组的最后一个元素在中序遍历数组中的位置，作为切割点
        int rootIndex=map.get(rootValue);

        //4.切割中序数组，切割点前的值构成左子树，切割点后的值构成右子树
        int lenOfLeft=rootIndex-inBegin;//左子树的长度
        //中序数组中左子树的区间为[inBegin,rootIndex),右子树的区间为[rootIndex+1,inEnd)

        //5.切割后序数组，切成后序左数组，后序右数组
        //后序数组中左子树的区间为[postBegin,postBegin+lenOfLeft),右子树的区间为[postBegin+lenOfLeft,postEnd-1)
        //6.递归处理左数组与右数组
        root.left=findNode(inorder,inBegin,rootIndex,postorder,postBegin,postBegin+lenOfLeft);
        root.right=findNode(inorder,rootIndex+1,inEnd,postorder,postBegin+lenOfLeft,postEnd-1);
        return root;
    }