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

解题思路:

首先还是定义哈希表将中序遍历的数插入进去，方便后序查阅
创建递归方法buildTreeNew(中序遍历数组，后序遍历数组，左或右子树在中序遍历数组中的起始和终止节点索引，左或右子树在后序遍历数组中的起始和终止节点索引)
后序遍历中最后一个数为二叉树的根节点
递归终止条件lastLeft>lastRight时候返回null

递归过程如下:

首先从后序遍历中找出根节点的值，再把根节点的值当作key查询哈希表得出根节点在中序遍历中的索引位置
创建根节点
递归创建左子树
传入参数中，左子树在中序遍历中的起始索引为中序遍历中第一个数的索引，终止索引为根节点midRoot-1,左子树在后序遍历中的起始索引为后序遍历中第一个数的索引，终止索引为起始索引+左子树的节点个数(通过中序遍历中根节点的索引-1-中序遍历中左子树的起始索引得出)。
递归创建右子树
传入参数中，右子树在中序遍历中的起始索引为midRoot+1，终止索引为midRight,在后序遍历中的起始索引为左子树在后序遍历中的终止索引+1，终止索引为lastRoot-1。
最后返回根节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    private Map<Integer,Integer> midMap;

    public TreeNode buildTreeNew(int[] inorder, int[] postorder,int midLeft,int midRight,int lastLeft,int lastRight)
    {
        if(lastLeft>lastRight) return null;
        //获取根节点在后序遍历中索引位置
        int lastRoot=lastRight;
        
        //左子树起始节点在后序遍历中的起始索引
        int startLeft=lastLeft;

        //获取根节点在中序遍历中的索引
        int midRoot=midMap.get(postorder[lastRoot]);
        //根据上一步算出左子树的节点个数
        int leftSize=midRoot-1-midLeft;

        //算出左子树在后序遍历中的终止索引
        int endLeft=startLeft+leftSize;

        //创建根节点
        TreeNode root=new TreeNode(postorder[lastRoot]);

        //递归创建左子树
        root.left=buildTreeNew(inorder,postorder,midLeft,midRoot-1,startLeft,endLeft);

        //递归创建右子树
        root.right=buildTreeNew(inorder,postorder,midRoot+1,midRight,endLeft+1,lastRight-1);

        return root;

    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        midMap =new HashMap<Integer,Integer>();

        int n=inorder.length;

        for(int i=0;i<n;i++)
        {
            midMap.put(inorder[i],i);
        }

        return buildTreeNew(inorder,postorder,0,n-1,0,n-1);
    }
}