【剑指offer】java实现前序中序重建二叉树
重建二叉树
http://www.nowcoder.com/questionTerminal/8a19cbe657394eeaac2f6ea9b0f6fcf6
1.思路
一开始看到这道题目我是一点思路都没有的，于是回想一下大学数据结构讲的如何通过前序遍历和中序遍历来画出二叉树。
- 首先想到前序遍历（先序遍历）的第一个数一定是二叉树的根节点
- 然后用这个数将中序遍历分成两半
- 最后利用中序遍历的左边和右边，把前序遍历中的后面一段拆成两段
- 回想一下参数列表
有了！这不就是不停的拆拆拆？好像根本不用手画（输出图形）吧？
那就简单了，本题专注于“拆数组”，然后利用题目给的reConstructBinaryTree递归就好。
弄完之后题目通过率为0.00%，检查算法发现思想是对的，确实不用关注画图。
于是就朝“特殊情况”想了，常见的特殊情况是“输入空值”和“输入特殊值”。就想到递归终止条件应当是数组pre或in为空。
- 算法终止前，数组的初始化语句应当是int[] inLeft=new int[0]，证明数组是初始化了的，所以处理数组为空的语句应该是inLeft.length==0而不是inLeft==null。
2.代码
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
//前序pre,中序in
if(pre.length!=0&&in.length!=0){
TreeNode treenode=new TreeNode(pre[0]);
int i=0;
while(pre[0]!=in[i]){
i++;
}//得到中序的根节点的下标i
//左右分割
int[] inLeft=new int[i];
int[] inRight=new int[in.length-i-1];
for (int j = 0; j < inLeft.length; j++) {
inLeft[j]=in[j];
}
for (int j = 0; j < inRight.length; j++) {
inRight[j]=in[j+inLeft.length+1];
}
int[] preLeft=new int[i];
int[] preRight=new int[in.length-i-1];
for (int j = 0; j < preLeft.length; j++) {
preLeft[j]=pre[1+j];
}
for (int j = 0; j < preRight.length; j++) {
preRight[j]=pre[j+preLeft.length+1];
}
treenode.left=reConstructBinaryTree(preLeft,inLeft);
treenode.right=reConstructBinaryTree(preRight,inRight);
return treenode;
}
else
return null;
}
} 😅第一次写题解，写的不好请多包涵，望各位看客提出一些改善方法。
