递归左子树,参数preEnd要传入:preStart+i-inStart,这个为什么要减inStart
递归右子树参数preStart要传入:preStart+i-inStart+1,这个为什么要减inStart
private static TreeNode reConstructBinaryTree(int[] pre,int preStart,int preEnd,int[] in,int inStart,int inEnd){
if(preStart>preEnd || inStart > inEnd){
return null;
}
TreeNode treeNode =new TreeNode(pre[preStart]);
for(int i=inStart;i<=inEnd;i++){
if(in[i] == pre[preStart]){
treeNode.lchild = reConstructBinaryTree( pre,preStart+1,preStart+i-inStart,in,inStart,i-1);
treeNode.rchild = reConstructBinaryTree(pre,preStart+i-inStart+1,preEnd,in,i+1,inEnd);
}
}
return treeNode;
}
随便举个例子就可以了:
前序:1 2 3 4 5
中序:2 3 1 4 5
前序可以定根,当前范围的第一个是根,但是不知道后续左子树右子树的长度
初始状态:
preStart=0,preEnd=4,inStart=0,inEnd=4
从前序中找到根是1,然后在中序0到4索引范围,找到索引2的值是2,于是对于中序数组,我们知道(0,1)是左子树(2,3)是右子树,其中,左子树的范围是2个元素,
那么可以把前序的接下来两个元素,考虑为前序的左子树,其余为右子树,
表达起来就是:
int len = i-inStart+1; //i为找到的索引2,左子树长度
int nextLeftPreEnd = (preStart+1)+( i-inStart+1);//起点+长度-1=终点,等价于prevStart+i-inStart;
int nextRightPreStart = nextLeftPreEnd+1;//其实题目那么写有点迷茫了,前序顺序就是【根,左子树,右子树】,所以排除掉左,紧接着后续就是右