题目:给定两个整数数组 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;
}