根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal
这个题目跟105题目的思路是一样的，不同的是这里使用的后续遍历序列，那么把后续反序之后就是：中序遍历左右子树交换的结果
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder.length==0)
return null;
HashMap<Integer,Integer> inorderMap=new HashMap<>();
for(int i=0;i<inorder.length;i++)
{
inorderMap.put(inorder[i],i);
}
return posBuild(inorder,postorder,inorderMap,0,inorder.length-1,0,postorder.length-1);
}
public TreeNode posBuild(int[] inorder, int[] postorder,HashMap<Integer,Integer> inorderMap,int inorderLeft,int inorderRight,int postLeft,int postRight)
{
if(postLeft>postRight)
return null;
int rootIndex=postRight;
int inorderRottIndex=inorderMap.get(postorder[rootIndex]);
TreeNode root=new TreeNode(postorder[rootIndex]);
int rightCount=inorderRight-inorderRottIndex;
root.right=posBuild(inorder,postorder,inorderMap,inorderRottIndex+1,inorderRight,postRight-rightCount,postRight-1);
root.left=posBuild(inorder,postorder,inorderMap,inorderLeft,inorderRottIndex-1,postLeft,postRight-rightCount-1);
return root;
}