重建二叉树:
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x){
val = x;
}
}
import java.util.HashMap; /**
* 先序数组： 1,2,4,7,3,5,6,8 中序数组：4,7,2,1,5,3,8,6
* 思路：1.先序数组中最左边的值就是树的头节点值，记为和，并且用h生成
* 头节点，记为head。然后在中序数组中找到h,假设位置为i。那么在
* 中序数组中，i左边的数组就是头节点左子树的中序数组，假设长度
* 为L,则左子树的先序数组就是先序数组中h往右长度也为L的数组
* 例如：二叉树头节点的值为1,在数组中找到1的位置，1的左边数组为
* 4,7,2 是头节点左子树的中序数组，长度为3； 先序数组中1的右边长度
* 也是3的数组为：2,4,7 ， 也就是左子树的先序数组。
* 2. 用左子树的先序和中序数组，递归整个过程建立左子树，返回的头节点记为left。
* 3. i右边的数组就是头结点右子树的中序数组，假设长度为r。先序数组中右侧等长
* 部分就是头节点右子树的先序数组。
* 例如：中序数组中1的右边数组为：5,3,8,6，长度为4； 先序数组右侧等长的部分为：
* 3,5,6,8,他们分别是头节点右子树的中序和先序数组。
* 4. 用右子树的先序和中序数组，递归整个过程建立右子树，返回的节点记为right。
* 5. 把head的左孩子和有孩子分别设为left和right,返回head,过程结束。
*
* 如果二叉树的节点数为N,在中序数组中找到位置i的过程可以用哈希表来实现，这样整个
* 过程时间复杂度为O(n)。
*/
public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre == null || in == null){
return null;
}
HashMap<Integer, Integer> map = new HashMap<>();
for(int i=0; i < in.length; i++){
map.put(in[i],i);
}
return preIn(pre, 0, pre.length -1 , in, 0, in.length -1, map);
} /**
* 递归函数
* @param p 前序数组
* @param pi 前序数组的初始下标
* @param pj 前序数组的结束下标
* @param n 中序数组
* @param ni 中序数组的初始下标
* @param nj 中序数组的结束下标
* @param map 中序值和位置的map集合
* @return
*/
public TreeNode preIn(int[] p, int pi, int pj, int[] n, int ni, int nj, HashMap<Integer,Integer> map){ if(pi > pj){
return null;
}
//头节点
TreeNode head = new TreeNode(p[pi]);
//头节点在中序的位置
int index = map.get(p[pi]);
head.left = preIn(p, pi + 1, pi + index - ni, n, ni, index -1, map);
head.right = preIn(p, pi + index - ni + 1, pj, n, index + 1, nj, map);
return head;
} }