解题思路:
首先还是定义哈希表将中序遍历的数插入进去,方便后序查阅
创建递归方法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);
}
}