题目描述
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
示例
提交的代码
思路：
轻喷，这种还是手写方便。
中序：左中右
后序：左右中
看我上面画的屎图，整棵树的根节点由后序的特性一定是在最后一个，也就是3，然后去中序数组可以确定3在哪，也就确定了整棵树的左子树和右子树有哪些节点，然后根据中序左子树和右子树的长度去确定后序数组中，左子树和右子树的后序遍历是哪些，然后去递归就行。
import java.util.Map;
import java.util.HashMap;
class Solution {
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 recursiveMethod(inorder,postorder,0,inorder.length-1,0,postorder.length-1);
}
public TreeNode recursiveMethod(int[] inorder, int[] postorder,int inLow,int inHigh,int postLow,
int postHigh){
//递归终止条件
if(inLow>inHigh){
return null;
}
TreeNode node=new TreeNode(postorder[postHigh]);
//根据后序遍历数组的最后一个元素来确定中序数组的索引值(划分左右树数组用)
int inNodeIndex=map.get(postorder[postHigh]);
//确定左子树的元素个数
int leftLength=inNodeIndex-inLow;
//确定右子树的元素个数
int rightLength=inHigh-inNodeIndex;
node.left=recursiveMethod(inorder,postorder,inLow,inNodeIndex-1,postLow,postLow+leftLength-1);
node.right=recursiveMethod(inorder,postorder,inNodeIndex+1,inHigh,postLow+leftLength,postHigh-1);
return node;
}
}