题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路：
首先需要明晰前序遍历，中序遍历，后序遍历的数组中能够给我们提供的潜在信息，首先前序遍历的第一个元素一定是整个树的根节点，而中序遍历中知道根节点，其根节点的前面的元素一定是整棵树的左子树的元素值，而后序遍历的最后一个元素一定是整棵树的根结点。所以要得出想要的答案，必须先得到根结点后根据根结点将中序遍历的数组分开，然后根据中序遍历的分开的数组，反过来将前序遍历的左子树和右子树分开，不断地递归就可以得到最终的原来的二叉树。
易错点：定义根结点的时候，只定义了根结点引用，用的时候直接让根结点的值等于前序遍历的值，这就导致了本来根结点为空又调用节点的值属性，导致了空指针异常。
源代码：
import java.util.ArrayList;
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
TreeNode left1;
TreeNode right0;
public TreeNode reConstructBinaryTree(int [] pre,int [] in)
{
//思路中序遍历的根节点是在遍历元素的中间，
//前序遍历的结果是在遍历元素的前面，
//元素必定为1，而根据中遍历结果可以推知中间位置分割出左右子树
//而返回的二叉树应该是层序遍历的结果
//因此这道题就变成了前序加中序推出层序的结果
//使用递归的方法找到根节点并不断的切割中序遍历的遍历元素
if(pre.length==0&&in.length==0)
{
return null;
}
TreeNode root=new TreeNode(pre[0]);
int i=0;
int j=0;
int k=0;
// ArrayList<Integer> preleft1 = new ArrayList<>();
// ArrayList<Integer> preright1 = new ArrayList<>();
// ArrayList<Integer> inleft1 = new ArrayList<>();
// ArrayList<Integer> inright = new ArrayList<>();
while(true)
{
if(pre[0]==in[j])
{
break;
}
j++;
}
int[] preleft1=new int[j];
int[] preright1=new int[pre.length-j-1];
int[] inleft1=new int[j];
int[] inright=new int[pre.length-j-1];
while(true)
{
if(pre[0]==in[i])
{
break;
}
preleft1[i]=pre[i+1];
inleft1[i]=in[i];
i++;
}
while(true)
{
if(i==pre.length-1)
{
break;
}
preright1[k]=pre[i+1];
inright[k]=in[i+1];
k++;
i++;
}
root.left=reConstructBinaryTree(preleft1,inleft1);
root.right=reConstructBinaryTree(preright1,inright);
return root;
}
}
