由中序、后续重建二叉树,我写的代码如下
在构建左右子树,被参数弄晕了,试了很多遍都抛出下标越界的异常,求大神指点!
public TreeNode constructCore(String behindOrder,String inOrder,int len,TreeNode root){
//前序遍历的第一个节点为根节点
TreeNode temp = new TreeNode();
temp.data = behindOrder.charAt(len-1);
temp.left = temp.right = null;
if(root == null) {
root = temp;
}
//判断只有一个节点的情况
if(len==1) {
return root;
}
//中序遍历中遍历找到根节点,计算子树的长度
int i = 0;
while(inOrder.charAt(i) != behindOrder.charAt(len-1)){
i++;
if(i > len) {
System.out.println("invalid input");
return null;
}
}
int leftLen = i;
int rightLen = len - leftLen - 1;
//构建二叉树
if(rightLen > 0) {//先构建右子树。参数这么传,调试发现没问题
root.right = constructCore(behindOrder.substring(0,len-1), inOrder, len, root.right);
}
if(leftLen > 0) {//构建左子树。参数这么传,感觉没错,但是抛出下标越界异常
//java是值传递,所以要重传root.left
root.left = constructCore(behindOrder.substring(0,rightLen+1), inOrder.substring(0,rightLen+1), leftLen, root.left);
}
return root;
}